[剑指offer-23]链表中环的入口节点

[23]链表中环的入口节点

1.题目

如果一个链表中包含环，如何找出环的入口节点？

2.思路

快慢指针扫描

1. 用两个指针first、second分别从起点开始走。
2. first每次走一步，second每次走两步
3. 如果过程中second走到null，说明没有环
4. 否则当 first 和 second 相遇后，让 first 返回起点，second 待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。

证明

$a$a 是起点，$b$b 是环的入口，$c$c 是两个指针的第一次相遇节点

• $ab$ab 之间的距离为 $x$x

• $bc$bc 之间的距离为 $y$y

• $cb$cb 之间顺时针距离为 $z$z

在第一次相遇时

first走的距离 $x+y$x+y

second走的距离 $x+n(z+y)+y$x+n(z+y)+y ，$n$n表示圈数

second走的距离是first的两倍
$x+n(z+y)+y = 2(x+y)\\ \Rightarrow x=(n−1)×(y+z)+z$x+n(z+y)+y=2(x+y)⇒x=(n−1)×(y+z)+z
那么：

让second从 $c$c 点走 $x$x 步，恰好到 $b$b

让first从 $a$a 点走 $x$x 步，也能到 $b$b

3.代码

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(!head || !head->next)  return 0;
        
        ListNode *first=head;
        ListNode *second=head;
        
        while(first && second)
        {
            first = first->next;
            second = second->next->next;  
          
            if(first==second) //相遇后，first返回head,first和second都只走一步
            {
                first=head;
                while(first != second)
                {
                    first = first->next;
                    second = second->next;
                }
                
                return first;
            }
        }
        return 0;
    }
};