本文讲解的例题
LeetCode 力扣 难度
- Linked List Cycle 141. 环形链表 🟢
- Linked List Cycle II 142. 环形链表 II 🟠
- Intersection of Two Linked Lists 160. 相交链表 🟢
- Remove Nth Node From End of List 19. 删除链表的倒数第 N 个结点 🟠
- Merge Two Sorted Lists 21. 合并两个有序链表 🟢
- Merge k Sorted Lists 23. 合并K个升序链表 🔴
- Partition List 86. 分隔链表 🟠
- Middle of the Linked List
- 链表的中间结点 🟢
剑指 Offer 22. 链表中倒数第k个节点 🟢
本文总结一下单链表的基本技巧，每个技巧都对应着至少一道算法题：
1、合并两个有序链表
2、链表的分解
3、合并 k 个有序链表
4、寻找单链表的倒数第 k 个节点
5、寻找单链表的中点
6、判断单链表是否包含环并找出环起点
7、判断两个单链表是否相交并找出交点
这些解法都用到了双指针技巧，所以说对于单链表相关的题目，双指针的运用是非常广泛的，下面我们就来一个一个看
合并两个有序链表
这是最基本的链表技巧，力扣第 21 题「合并两个有序链表」就是这个问题，给你输入两个有序链表，请你把他俩合并成一个新的有序链表：
- 链表的中间结点 🟢
- 合并两个有序链表 | 力扣 | LeetCode | 🟢
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
● 两个链表的节点数目范围是 [0, 50]
● -100 <= Node.val <= 100
● l1 和 l2 均按 非递减顺序 排列
// 函数签名如下
ListNode mergeTwoLists(ListNode l1, ListNode l2);
这题比较简单，我们直接看解法：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = l1, p2 = l2;
while (p1 != null && p2 != null) {
// 比较 p1 和 p2 两个指针
// 将值较小的的节点接到 p 指针
if (p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
// p 指针不断前进
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
}
我们的 while 循环每次比较 p1 和 p2 的大小，把较小的节点接到结果链表上，看如下 GIF：
形象地理解，这个算法的逻辑类似于拉拉链，l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并。
代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。你可以试试，如果不使用 dummy 虚拟节点代码会复杂一些，需要额外处理指针 p 为空的情况。而有了dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。
何时使用虚拟头结点
经常有读者问我，什么时候需要用虚拟头结点？我这里总结下：当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。
比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。
单链表的分解
- 分隔链表 | 力扣 | LeetCode | 🟠
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置 [这块有点抽象]
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
● 链表中节点的数目在范围 [0, 200] 内
● -100 <= Node.val <= 100
● -200 <= x <= 200
在合并两个有序链表时让你合二为一，而这里需要分解让你把原链表一分为二。具体来说，我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。
整体逻辑和合并有序链表非常相似，细节直接看代码吧，注意虚拟头结点的运用：、
class Solution {
public ListNode partition(ListNode head, int x) {
// 存放小于 x 的链表的虚拟头结点
ListNode dummy1 = new ListNode(-1);
// 存放大于等于 x 的链表的虚拟头结点
ListNode dummy2 = new ListNode(-1);
// p1, p2 指针负责生成结果链表
ListNode p1 = dummy1, p2 = dummy2;
// p 负责遍历原链表，类似合并两个有序链表的逻辑
// 这里是将一个链表分解成两个链表
ListNode p = head;
while (p != null) {
if (p.val >= x) {
p2.next = p;
p2 = p2.next;
} else {
p1.next = p;
p1 = p1.next;
}
// 不能直接让 p 指针前进，
// p = p.next
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;
}
// 连接两个链表
p1.next = dummy2.next;
return dummy1.next;
}
}
我知道有很多读者会对这段代码有疑问：
// 不能直接让 p 指针前进，
// p = p.next
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;
如果你不断开原链表中的每个节点的 next 指针，那么就会出错，因为结果链表中会包含一个环。总的来说，如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。那其实我们可以养成一个好习惯，但凡遇到这种情况，就把原链表的节点断开，这样就不会出错了
合并k个有序链表
- 合并 K 个升序链表 | 力扣 | LeetCode | 🔴
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
// 函数签名如下
ListNode mergeKLists(ListNode[] lists);
合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于如何快速得到 k 个节点中的最小节点，接到结果链表上？这里我们就要用到优先级队列这种数据结构，把链表节点放入一个最小堆，就可每次获得 k 个节点中最小节点。关于优先级队列可参考 优先级队列（二叉堆）原理及实现，本文不展开。
