程序员到管理千人团队的CTO

接下来我们聊聊 dummy node 这个技巧。

Dummy node

Dummy 的中文是“假”的意思，dummy node 大概可以翻译成虚拟节点？有更地道的说法的话还请大家在评论区告诉我呀～

一般来说，dummy node 的用法是在链表的真实 head 的前面加一个指向这个 head 的节点，目的是为了方便操作 head。

对于链表来说，head 是一个链表的灵魂，因为无论是查询还是其他的操作都需要从头开始，俗话说擒贼先擒王嘛，抓住了一个链表的头，就抓住了整个链表。

所以当需要对现有链表的头进行改动时，或者不确定头部节点是哪个，我们可以预先加一个 dummyHead，这样就可以灵活处理链表中的剩余部分，最后返回时去掉这个“假头”就好了。

很多时候 dummy node 不是必须，但是用了会很方便，减少 corner case 的讨论，所以还是非常推荐使用的。

光说不练假把式，我们直接来看题～

例 4：合并两个排好序的链表
 

这题我感觉不全是个算法题了，还是个数学题哈哈。

先摆出结论：

1.  快慢指针从链表头开始走，相遇的那点，记为 M；
2.  再用 2 个指针，一个从头开始走，一个从 M 开始走，相遇点即为 cycle 的起点。

我们先看抽象出来的图：

假设快慢指针在 M 点第一次相遇，

这里我们设 3 个变量来表示这个链表里的几个重要长度：

•  X：从链表头到环的起点的长度；
•  Y：从环的起点到 M 点的长度；
•  Z：从 M 点到环的起点的长度。

注意：因为环是有方向的，所以 Y 并不是 Z。

那其实我们唯一知道的关系就是：快慢指针在 M 点第一次相遇。这也是我们最初假设的关系。

而快慢指针有一个永远不变的真理：快指针走的长度永远是慢指针走的长度的 2 倍。

相遇时快慢指针分别走了多少的长度呢？

•  快指针：X+ Y + 假设走了 k 圈
•  慢指针：X + Y

那么我们就可以用这个 2 倍的关系，列出下列等式：

2 * (X + Y) = X + Y + kL

所以 X + Y = kL

而我们注意到：Y + Z = L，那么就能得出 X = Z。

所以当两个指针，一个从头开始走，一个从 M 点开始走时，相遇那点就是环的起点，证毕。

来看下代码吧：

（编辑：四平站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!