双指针秒杀七道链表题

AI summary

type

status

date

slug

summary

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

很简单，直接归并就行了，两个指针分别指向两个链表，一个指针指向新的链表。别忘了把剩下的给接上。

当需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起。

如果我们需要把原链表的节点接到新链表上，而不是 new 新节点来组成新链表的话，那么断开节点和原链表之间的链接可能是必要的。比如这里如果没有 p2.next = None，那么 p2.next 就连到了第一个链表上，构成了环。

23. 合并 K 个升序链表

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

如何快速得到 k 个节点中的最小节点，接到结果链表上？

使用优先级队列，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点。Python 中优先队列需要用 heapq 包。

也可以通过重载运算符实现自定义比较：

但是核心代码模式的 OJ 用不了。所以这里使用元组作为最小堆的元素，会按每个元组的第一个元素排序。如果要用最大堆，可以入队时取个负数。

这个算法是面试常考题，它的时间复杂度是多少呢？

优先队列 pq 中的元素个数最多是 k，所以一次 push 或者 pop 方法的时间复杂度是；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 ，其中 k 是链表的条数，N 是这些链表的节点总数。

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

可以一次扫描实现。

首先是找到倒数第 k 个节点的算法：首先让 p1 指向 head，先走 k 步，然后让 p2 指向 head，和 p1 同步走。当 p1 走到 None 时 p2 所在的位置就是倒数第 k 个节点。原理如下图：

在这个题目中，只需要找到倒数第 n+1 个节点，然后删除第 n 个节点即可。

注意最后返回的是 dummy.next 不是 head，因为 head 也可能被删。

876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧：

让两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
不允许修改 链表。

也是快慢指针，原理如下图：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

可以看到，当快慢指针相遇时，让其中任一指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

如果 fast 能走到头，那就没有环。

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应。所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

还有个比较投机的方法，如果把两条链表首尾相连，那么「寻找两条链表的交点」的问题转换成了前面讲的「寻找环起点」的问题：

但是注意题目要求必须保持原始结构，所以得到答案之后需要变回来。

语法

slow = fast = head 是链式赋值，变量是逐个赋值的。

slow, fast = head, head 是解包赋值，变量是同时赋值的。

虽然在这个例子中两者的效果是一样的，但解包赋值更通用，可以用于同时赋值不同的值，例如：

1. 如果 slow 和 fast 指向的是同一个可变对象

在这种情况下，如果你通过 slow 修改了对象的内容（而不是重新赋值），fast 会感知到变化，因为它们指向的是同一个对象。

示例：

在这个例子中，slow 和 fast 都指向同一个列表对象，因此通过 slow 修改列表内容时，fast 也会感知到变化。

2. 如果你对 slow 重新赋值

如果你对 slow 重新赋值（让它指向一个新的对象），fast 不会跟着变，因为此时 slow 和 fast 已经指向了不同的对象。

示例：

在这个例子中，slow 被重新赋值为一个新的列表 [4, 5, 6]，但 fast 仍然指向原来的 head，因此它们不再相关。