算法:链表中环的入口结点

链表中环的入口结点

链表中环的入口结点

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

分析

快慢指针的方法;

首先快慢指针都从头开始, 快指针每次两步, 慢指针每次一步;

如果两个指针最终相遇, 则说明链表存在环!

此时快指针从当前继续向前走(每次一步), 而慢指针从链表头开始走(每次一步), 最终两个指针会相遇在入口节点;

可以通过计算两个指针的路程来证明;

简单证明一下:

设：

• 链表头到环入口长度为–a
• 环入口到相遇点长度为–b
• 相遇点到环入口长度为–c

则：相遇时:

快指针路程=a+(b+c)k+b

k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。

慢指针路程=a+b

快指针走的路程是慢指针的两倍，所以：

（a+b）*2=a+(b+c)k+b

化简可得：

a=(k-1)(b+c)+c

这个式子的意思是：链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度

其中k>=1,所以为k-1>=0圈。

所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。

代码

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 有环
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}