【优选算法】（第二十七篇）

目录

重排链表（medium）

题目解析

讲解算法原理

编写代码

合并K个升序链表（hard）

题目解析

讲解算法原理

编写代码

---

重排链表（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个单链表 L 的头节点 head ，单链表 L 表⽰为：L(0)→L(1)→…→L(n-1)→L(n)
请将其重新排列后变为：
L(0)→L(n)→L(1)→L(n-1)→L(2)→L(n-2)→…
不能只是单纯的改变节点内部的值，⽽是需要实际的进⾏节点交换。
⽰例1：

输⼊：head=[1,2,3,4]
输出：[1,4,2,3]
⽰例2：

输⼊：head=[1,2,3,4,5]
输出：[1,5,2,4,3]

提⽰：
• 链表的⻓度范围为 [1, 5 * 10(4)]
• 1 <= node.val <= 1000

讲解算法原理

解法：
算法思路：
画图画图画图，重要的事情说三遍~
1. 找中间节点；
2. 中间部分往后的逆序；
3. 合并两个链表

编写代码

c++算法代码：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution
{
public:void reorderList(ListNode* head) {// 处理边界情况if(head == nullptr || head->next == nullptr || head->next->next == 
nullptr) return;// 1. 找到链表的中间节点 - 快慢双指针（⼀定要画图考虑 slow 的落点在哪⾥） ListNode* slow = head, *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}// 2. 把 slow 后⾯的部分给逆序 - 头插法ListNode* head2 = new ListNode(0);ListNode* cur = slow->next;slow->next = nullptr; // 注意把两个链表给断开while(cur){ListNode* next = cur->next;cur->next = head2->next;head2->next = cur;cur = next;}// 3. 合并两个链表 - 双指针ListNode* ret = new ListNode(0);ListNode* prev = ret;ListNode* cur1 = head, *cur2 = head2->next;while(cur1){// 先放第⼀个链表prev->next = cur1;cur1 = cur1->next;prev = prev->next;// 再放第⼆个链表if(cur2){prev->next = cur2;prev = prev->next;cur2 = cur2->next;}}delete head2;delete ret;}
};

java算法代码：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution
{public void reorderList(ListNode head) {// 处理边界情况if(head == null || head.next == null || head.next.next == null) return;// 1. 找链表的中间节点 - 快慢双指针（⼀定要画图分析 slow 的落点）ListNode slow = head, fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}// 2. 把 slow 后⾯的部分给逆序 - 头插法ListNode head2 = new ListNode(0);ListNode cur = slow.next;slow.next = null; // 把两个链表分离while(cur != null){ListNode next = cur.next;cur.next = head2.next;head2.next = cur;cur = next;}// 3. 合并两个链表 - 双指针ListNode cur1 = head, cur2 = head2.next;ListNode ret = new ListNode(0);ListNode prev = ret;while(cur1 != null){// 先放第⼀个链表prev.next = cur1;prev = cur1;cur1 = cur1.next;// 在合并第⼆个链表if(cur2 != null){prev.next = cur2;prev = cur2;cur2 = cur2.next;}}}
}

合并K个升序链表（hard）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到⼀个升序链表中，返回合并后的链表。
⽰例1：

输⼊：lists=[[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：[
1->4->5,
1->3->4,
2->6
]
将它们合并到⼀个有序链表中得到。1->1->2->3->4->4->5->6
⽰例2：输⼊：lists=[]输出：[]
⽰例3：输⼊：lists=[[]]输出：[]

提⽰：k==lists.length0<=k<=10^40<=lists[i].length<=500-10^4<=lists[i][j]<=10^4lists[i]按升序排列
lists[i].length的总和不超过10^4

讲解算法原理

解法⼀（利⽤堆）：

算法思路：

合并两个有序链表是⽐较简单且做过的，就是⽤双指针依次⽐较链表 1 、链表 2 未排序的最⼩元素，选择更⼩的那⼀个加⼊有序的答案链表中。
合并 K 个升序链表时，我们依旧可以选择 K 个链表中，头结点值最⼩的那⼀个。那么如何快速的得到头结点最⼩的是哪⼀个呢？⽤堆这个数据结构就好啦~
我们可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次 K 个链表中，最⼩的元素是哪个。

解法⼆（递归/分治）：

算法思路：
逐⼀⽐较时，答案链表越来越⻓，每个跟它合并的⼩链表的元素都需要⽐较很多次才可以成功排序。⽐如，我们有8个链表，每个链表⻓为100。
逐⼀合并时，我们合并链表的⻓度分别为(0,100),(100,100),(200,100),(300,100),(400,100),(500,100),(600,100),(700,100)。所有链表的总⻓度共计3600。
如果尽可能让⻓度相同的链表进⾏两两合并呢？这时合并链表的⻓度分别是(100,100)x4,(200,200)x2,(400,400)，共计2400。⽐上⼀种的计算量整整少了1/3。
迭代的做法代码细节会稍多⼀些，这⾥给出递归的实现，代码相对简洁，不易写错。
算法流程：
1. 特判，如果题⽬给出空链表，⽆需合并，直接返回；
2. 返回递归结果。
递归函数设计：
1. 递归出⼝：如果当前要合并的链表编号范围左右值相等，⽆需合并，直接返回当前链表；2. 应⽤⼆分思想，等额划分左右两段需要合并的链表，使这两段合并后的⻓度尽可能相等；3. 对左右两段分别递归，合并[l,r]范围内的链表；
4. 再调⽤mergeTwoLists函数进⾏合并（就是合并两个有序链表）

编写代码

解法一代码：

c++算法代码：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution
{struct cmp{bool operator()(const ListNode* l1, const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {// 创建⼀个⼩根堆priority_queue<ListNode*, vector<ListNode*>, cmp> heap;// 让所有的头结点进⼊⼩根堆for(auto l : lists)if(l) heap.push(l);// 合并 k 个有序链表ListNode* ret = new ListNode(0);ListNode* prev = ret;while(!heap.empty()){ListNode* t = heap.top();heap.pop();prev->next = t;prev = t;if(t->next) heap.push(t->next);}prev = ret->next;delete ret;return prev;}
};

java算法代码：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution
{public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val 
- v2.val);// 将所有头结点加⼊到⼩根堆中for(ListNode l : lists)if(l != null)heap.offer(l);// 合并ListNode ret = new ListNode(0);ListNode prev = ret;while(!heap.isEmpty()){ListNode t = heap.poll();prev.next = t;prev = t;if(t.next != null) heap.offer(t.next);}return ret.next;}
}

解法二代码：

c++算法代码：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution
{
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}ListNode* merge(vector<ListNode*>& lists, int left, int right){if(left > right) return nullptr;if(left == right) return lists[left];// 1. 平分数组int mid = left + right >> 1;// [left, mid] [mid + 1, right]// 2. 递归处理左右区间ListNode* l1 = merge(lists, left, mid);ListNode* l2 = merge(lists, mid + 1, right);// 3. 合并两个有序链表return mergeTowList(l1, l2);}ListNode* mergeTowList(ListNode* l1, ListNode* l2){if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;// 合并两个有序链表ListNode head;ListNode* cur1 = l1, *cur2 = l2, *prev = &head;head.next = nullptr;while(cur1 && cur2){if(cur1->val <= cur2->val){prev = prev->next = cur1;cur1 = cur1->next;}else{prev = prev->next = cur2;cur2 = cur2->next;}}if(cur1) prev->next = cur1;if(cur2) prev->next = cur2;return head.next;}
};

java算法代码：

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution
{public ListNode mergeKLists(ListNode[] lists) {return merge(lists, 0, lists.length - 1);}public ListNode merge(ListNode[] lists, int left, int right){if(left > right) return null;if(left == right) return lists[left];// 1. 平分数组int mid = (left + right) / 2;// [left, mid] [mid + 1, right]// 2. 递归处理左右两部分ListNode l1 = merge(lists, left, mid);ListNode l2 = merge(lists, mid + 1, right);// 3. 合并两个有序链表return mergeTwoList(l1, l2);}public ListNode mergeTwoList(ListNode l1, ListNode l2){if(l1 == null) return l2;if(l2 == null) return l1;// 合并两个有序链表ListNode head = new ListNode(0);ListNode cur1 = l1, cur2 = l2, prev = head;while(cur1 != null && cur2 != null){if(cur1.val <= cur2.val){prev.next = cur1;prev = cur1;cur1 = cur1.next;}else{prev.next = cur2;prev = cur2;cur2 = cur2.next;}}if(cur1 != null) prev.next = cur1;if(cur2 != null) prev.next = cur2;return head.next;}
}