每日算法-链表(23.合并k个升序链表、25.k个一组翻转链表)

一.合并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;}
};