链表中环的入口结点

题目 #

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

解题思路 #

  1. 首先通过 快慢指针(快:每次走两步;慢:每次走一步)确定是否有环
  2. 当有环时,再从头节点出发,与快指针按 相同速度 向前移动,当 cursor = fast 则找到环入口
public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null) return null;

    ListNode fast = pHead, slow = pHead;

    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (fast == slow) break;
    }

    if (fast != slow) return null;

    ListNode cursor = pHead;
    while (cursor != fast) {
        cursor = cursor.next;
        fast = fast.next;
    }

    return cursor;
}