[剑指offer] 链表中环的入口结点

本文首发于我的个人博客： 尾尾部落

题目描述

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

解题思路

第一步，用两个快慢指针找环中相汇点。分别用

slow

,

fast

指向链表头部，

slow

每次走一步，

fast

每次走二步，直到

fast == slow

找到在环中的相汇点。

第二步，找环的入口。当

fast == slow

时，假设

slow

走过x个节点，则

fast

走过2x个节点。设环中有n个节点，因为

fast

比

slow

多走一圈（n个节点），所以有等式

2x = n + x

，可以推出

n = x

，即

slow

实际上走了一个环的步数。这时，我们让

fast

重新指向链表头部

pHead

，

slow

的位置不变，然后

slow

和

fast

一起向前每次走一步，直到

fast == slow

，此时两个指针相遇的节点就是环的入口。

参考代码

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if(pHead.next == null || pHead.next.next == null)
            return null;
        ListNode slow = pHead.next;
        ListNode fast = pHead.next.next;
        while(fast != null){
            if(fast == slow){
                fast = pHead;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return null;
    }
}