每日一题《剑指offer》链表篇之合并k个已排序的链表
合并k个已排序的链表
难度：困难
描述
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围
数据范围：节点总数 0≤n≤5000，每个节点的val满足 ∣val∣<=1000
要求：时间复杂度O(nlogn)
举例
解题思路
方法一:归并排序 如果是两个有序链表合并，我们可能会利用归并排序合并阶段的思想：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。
其实这道题我们也可以两两比较啊，只要遍历链表数组，取出开头的两个链表，按照上述思路合并，然后新链表再与后一个继续合并，如此循环，知道全部合并完成。但是，这样太浪费时间了。
既然都是归并排序的思想了，那我们可不可以直接归并的分治来做，而不是顺序遍历合并链表呢？答案是可以的！
归并排序是什么？简单来说就是将一个数组每次划分成等长的两部分，对两部分进行排序即是子问题。对子问题继续划分，直到子问题只有1个元素。还原的时候呢，将每个子问题和它相邻的另一个子问题利用上述双指针的方式，1个与1个合并成2个，2个与2个合并成4个，因为这每个单独的子问题合并好的都是有序的，直到合并成原本长度的数组。
对于这k个链表，就相当于上述合并阶段的k个子问题，需要划分为链表数量更少的子问题，直到每一组合并时是两两合并，然后继续往上合并，这个过程基于递归：
- 终止条件： 划分的时候直到左右区间相等或左边大于右边。
- 返回值： 每级返回已经合并好的子问题链表。
- 本级任务： 对半划分，将划分后的子问题合并成新的链表。
具体做法：
- step 1：从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半，得到左边n/2n/2n/2个链表和右边n/2n/2n/2个链表。
- step 2：继续不断递归划分，直到每部分链表数为1.
- step 3：将划分好的相邻两部分链表，按照两个有序链表合并的方式合并，合并好的两部分继续往上合并，直到最终合并成一个链表。
方法二:优先队列 如果非要按照归并排序的合并思路，双指针不够用，我们可以直接准备kkk个指针，每次比较得出kkk个数字中的最小值。为了快速比较kkk个数字得到最小值，我们可以利用Java提供的PriorityQueue或者C++SLT提供的优先队列或者Python提供的PriorityQueue可以实现，它是一种参照堆排序的容器，容器中的元素是有序的，如果是小顶堆，顶部元素就是最小的，每次可以直接取出最小的元素。也就是说
每次该容器中有k个元素，我们可以直接拿出最小的元素，再插入下一个元素，相当于每次都是链表的k个指针在比较大小，只移动最小元素的指针。
具体做法：
- step 1：不管是Java还是C++都需要重载比较方法，构造一个比较链表节点大小的小顶堆。（Python版本直接加入节点值）
- step 2：先遍历k个链表头，将不是空节点的节点加入优先队列。
- step 3：每次依次弹出优先队列中的最小元素，将其连接在合并后的链表后面，然后将这个节点在原本链表中的后一个节点（如果不为空的话）加入队列，类似上述归并排序双指针的过程。
实现代码（java）
方法一:
import java.util.ArrayList; public class Solution { //两个链表合并函数 public ListNode Merge(ListNode list1, ListNode list2) { //一个已经为空了，直接返回另一个 if(list1 == null) return list2; if(list2 == null) return list1; //加一个表头 ListNode head = new ListNode(0); ListNode cur = head; //两个链表都要不为空 while(list1 != null && list2 != null){ //取较小值的节点 if(list1.val <= list2.val){ cur.next = list1; //只移动取值的指针 list1 = list1.next; }else{ cur.next = list2; //只移动取值的指针 list2 = list2.next; } //指针后移 cur = cur.next; } //哪个链表还有剩，直接连在后面 if(list1 != null) cur.next = list1; else cur.next = list2; //返回值去掉表头 return head.next; } //划分合并区间函数 ListNode divideMerge(ArrayList<ListNode> lists, int left, int right){ if(left > right) return null; //中间一个的情况 else if(left == right) return lists.get(left); //从中间分成两段，再将合并好的两段合并 int mid = (left + right) / 2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right)); } public ListNode mergeKLists(ArrayList<ListNode> lists) { //k个链表归并排序 return divideMerge(lists, 0, lists.size() - 1); } }
方法二:
import java.util.*; public class Solution { public ListNode mergeKLists(ArrayList<ListNode> lists) { //小顶堆 Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val); //遍历所有链表第一个元素 for(int i = 0; i < lists.size(); i++){ //不为空则加入小顶堆 if(lists.get(i) != null) pq.add(lists.get(i)); } //加一个表头 ListNode res = new ListNode(-1); ListNode head = res; //直到小顶堆为空 while(!pq.isEmpty()){ //取出最小的元素 ListNode temp = pq.poll(); //连接 head.next = temp; head = head.next; //每次取出链表的后一个元素加入小顶堆 if(temp.next != null) pq.add(temp.next); } //去掉表头 return res.next; } }
学习完本题的思路你可以解决如下题目：
判断链表中是否有环
难度：中等
描述
判断给定的链表中是否有环。如果有环则返回true，否则返回false。
数据范围
数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足∣val∣<=100000
要求：空间复杂度 O(1)，时间复杂度 O(n)
举例
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：
可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
解题思路
方法一:双指针 我们都知道链表不像二叉树，每个节点只有一个val值和一个next指针，也就是说一个节点只能有一个指针指向下一个节点，不能有两个指针，那这时我们就可以说一个性质：环形链表的环一定在末尾，末尾没有NULL了。为什么这样说呢？仔细看上图，在环2，0，-4中，没有任何一个节点可以指针指出环，它们只能在环内不断循环，因此环后面不可能还有一条尾巴。如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。
但是，环形链表遍历过程中会不断循环，线形链表遍历到NULL结束了，但是环形链表何时能结束呢？我们可以用双指针技巧，同向访问的双指针，速度是快慢的，只要有环，二者就会在环内不断循环，且因为有速度差异，二者一定会相遇。
具体做法：
- step 1：设置快慢两个指针，初始都指向链表头。
- step 2：遍历链表，快指针每次走两步，慢指针每次走一步。
- step 3：如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为NULL。
- step 4：如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。
实现代码（java）
方法一:
public class Solution { public boolean hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return false; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环 if(fast == slow) return true; } //到末尾则没有环 return false; } }
学习完本题的思路你可以解决如下题目：
链表中倒数最后k个节点
难度：中等
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围
数据范围：0≤n≤105，0≤ai≤109，0≤k≤109
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
举例
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
解题思路
方法一:快慢双指针 我们无法逆序遍历链表，就很难得到链表的倒数第kkk个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第kkk的位置上，即距离链表尾的距离是kkk，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是kkk。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施。
具体做法：
- step 1：准备一个快指针，从链表头开始，在链表上先走kkk步。
- step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是kkk。
- step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数kkk个元素的位置。
方法二:先找长度再找最后k 链表不能逆向遍历，也不能直接访问。但是对于倒数第kkk个位置，我们只需要知道是正数多少位还是可以直接遍历得到的。
具体做法：
- step 1：可以先遍历一次链表找到链表的长度。
- step 2：然后比较链表长度是否比kkk小，如果比kkk小返回一个空节点。
- step 3：如果链表足够长，则我们从头节点往后遍历n−kn-kn−k次即可找到所求。
实现代码（java）
方法一:
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { int n = 0; ListNode fast = pHead; ListNode slow = pHead; //快指针先行k步 for(int i = 0; i < k; i++){ if(fast != null) fast = fast.next; //达不到k步说明链表过短，没有倒数k else return slow = null; } //快慢指针同步，快指针先到底，慢指针指向倒数第k个 while(fast != null){ fast = fast.next; slow = slow.next; } return slow; } }
方法二:
import java.util.*; public class Solution { public ListNode FindKthToTail (ListNode pHead, int k) { int n = 0; ListNode p = pHead; //遍历链表，统计链表长度 while(p != null){ n++; p = p.next; } //长度过小，返回空链表 if(n < k) return null; p = pHead; //遍历n-k次 for(int i = 0; i < n - k; i++) p = p.next; return p; } }
