【剑指Offer】23. 链表中环的入口结点

妖狐艹你老母 2022-11-25 13:08 102阅读 0赞

[NowCoder][]

## 题目描述 ##

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。

## 解题思路 ##

使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。

在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
    public class Solution { 
    
        public ListNode EntryNodeOfLoop(ListNode pHead) { 
            if(pHead == null || pHead.next == null)
                return null;
            
            ListNode fast = pHead, slow = pHead;
            do{ 
                fast = fast.next.next;
                slow = slow.next;
            }while(fast != slow);
            
            // 此时x=z（fast从头节点开始，slow从第一次相遇z点开始。下一次相遇则是入口）
            fast = pHead;
            while(fast != slow) { 
                fast = fast.next;
                slow = slow.next;
            }
           
            return slow;
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11208&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]: /images/20221124/70dda6feee5c4c8e926c7154b5cee900.png