链表中环的入口结点

题目

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出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;
    }