一.合并k個升序鏈表
1.1題目描述
1.2題解思路
解法一：小根堆
我們可以先定義一個小根堆，將k個指針的頭結點如堆，每次取堆頂元素尾插到newhead中，然后再pop()，接著push堆頂原來堆頂元素的下一個節點
重點分析：
1.定義小根堆的時候需要傳入仿函數。
2.每次入堆之前需要判斷指針是否為空
3.循環結束條件為堆空
解法二：遞歸
用遞歸的思想，將k個鏈表分成兩份，先分別合并這兩份鏈表，再合并這兩個有序的鏈表
1.3題解代碼
解法一代碼：
class Solution {
public:class cmp{public:bool operator()(ListNode * l1,ListNode *l2){return l1->val > l2->val;} };ListNode* mergeKLists(vector<ListNode*>& lists) {//定義小根堆priority_queue<ListNode *,vector<ListNode *>,cmp> heap;ListNode* newhead = new ListNode(-1);ListNode* cur = newhead;//讓所有的頭結點進入小根堆for(int i = 0;i < lists.size();i++){if(lists[i])heap.push(lists[i]);}//合并k個有序鏈表while(!heap.empty()){ListNode* tmp = heap.top();cur->next = tmp;cur = cur->next;tmp = tmp->next;heap.pop();if(tmp)heap.push(tmp);}return newhead->next;}
};解法二代碼:
class Solution {
public://將[left,right)區間的鏈表排序，并且返回頭結點ListNode* _mergeKLists(vector<ListNode*>& lists,int left,int right){if(left > right) return nullptr;if(left == right) return lists[left];ListNode* newhead = new ListNode(-1);ListNode* cur = newhead;//[left,tmp][tmp+1,right]int tmp = (left+right)/2;ListNode* l1 = _mergeKLists(lists,left,tmp);ListNode* l2 = _mergeKLists(lists,tmp+1,right);//合并兩個有序鏈表while(l1 && l2){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;cur = cur->next;}else{cur->next = l2;l2 = l2->next;cur = cur->next;}}if(l1) cur->next = l1;if(l2) cur->next = l2;ListNode* ret = newhead->next;delete newhead;return ret;}ListNode* mergeKLists(vector<ListNode*>& lists) {return _mergeKLists(lists,0,lists.size() - 1);}
};二.k個一組翻轉鏈表
2.1題目描述
2.2題解思路
1.先求出需要翻轉多少組 n
2.以k個為一組，翻轉n次
2.3題解代碼
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* newhead = new ListNode(-1);//1.求出需要翻轉多少次ListNode* cur = head;int size = 0;while(cur){cur = cur->next;size++;}int n =size/k;//重復n次，以k個為一組翻轉鏈表cur = head;ListNode* prev = newhead;ListNode* next = cur->next;while(n--){ListNode* tmp = cur;//翻轉鏈表for(int i = 0; i <k; i++){cur->next = prev->next;prev->next = cur;cur = next;if(next) next = next->next;}prev = tmp;}//把不需要翻轉的接上prev->next = cur;return newhead->next;}
};
