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

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

链表中环的入口

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

若其中不包含环,则输出 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

HEADEntrance 之间的距离为 $X$ ,Entranceptr 之间的距离为 $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;
  }
}