LC-141和LC-142有哪些区别？

本文共计656个文字，预计阅读时间需要3分钟。

142. 简化环形链表 II 思路：设链表共有 a+b 个节点，其中从链表头部到入口有 a 个节点（不包括入口节点），环中有 b 个节点。再设两个指针分别指向 f 和 s，分别从入口和头部出发，同时移动。则有两种情况：

1.f 和 s 相遇时，f 所走过的距离为 f=2s

2.s 到达尾部，此时 f 也到达尾部，f 所走过的距离为 2s=2s

142. 环形链表 II

思路：

设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。

再设两指针分别走了 f，s 步，则有：

• f = 2sf=2s；
• fast 比 slow多走了 n 个环的长度，即 f = s + nbf=s+nb；
• 以上两式相减得：f = 2nbf=2nb，s = nbs=nb；

概括一下：

根据：

1. f=2s （快指针每次2步，路程刚好2倍）
2. f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步。