链表中环的入口 -- 剑指 Offer

链表中环的入口 -- 剑指 Offer

Administrator 458 2020-11-06

链表中环的入口

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出 null

样例

pic

给定如上所示的链表：

[1, 2, 3, 4, 5, 6]
2

注意，这里的 2 表示编号是 2 的节点，节点编号从 0 开始。所以编号是 2 的节点就是 val 等于 3 的节点。

则输出环的入口节点 3 .

思路及证明过程

  • 快慢指针法
graph LR f{FAST} -->|2| 1((HEAD)) -->|X| 2((Entrance)) -->|Y| 3((ptr)) -->|Z| 4((net)) --> |Y| 2((Entrance)) s{SLOW} -->|1| 1((HEAD))

设两指针初始化指向 HEAD 节点，指针 每次移动 1 位，另一指针每次移动 2 位，它们先后进入环中（如果有环的话），并必然相遇于节点 ptr

设 HEAD 与 Entrance 之间的距离为 $X$ ，Entrance 与 ptr 之间的距离为 $Y$ ，当其相遇时，此时有 $L_=2(X + Y)$, $L_ = X + Y$

令 $P_=1$ 退 $Y$ 步到达 Entrance ，则 $P_$ 回退 $2Y$ 步到达 net ，则此时 $L_{HEAD->net} = 2X$ , 且有 $L_{HEAD->Entrance} = X$ ，则有 $L_{Entrance->net} = X$ ，则可得出 $L_{Entrance->Entrance} = X + Y$

故只需令一节点 $P_$ 返回 HEAD 节点，并使 $P_$ 位移步长为 1 ，$P_$ 在 ptr 继续移动直到其相遇，相遇点就是环的入口

graph LR 1((HEAD)) -->|X| 2((Entrance)) -->|Y| 3((ptr)) -->|Z| 4((net)) --> |Y| 2((Entrance))

Code

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
  public ListNode entryNodeOfLoop(ListNode head) {
    ListNode ptr = head, net = head;
    while (ptr != null && net != null) {
      ptr = ptr.next; net = net.next;
      if (net != null) {
        net = net.next;
        if (net == null) return null;
      }
      if (ptr == net) {
        ptr = head;
        while(ptr != net) {
          ptr = ptr.next;
          net = net.next;
        }
        return net;
      }
    }
    return null;
  }
}
Algorithm