剑指offer最优解Java版-链表中环的入口结点

题目描述

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

解决方法

两个阶段：

1. 让快慢指针一起走，直到两个相遇。
2. 假设从起点到环入口处距离为m，慢指针从环入口处继续走x距离，与快指针相遇。则将两个指针速度都变成每次一格，然后A指针从相遇点继续出发，B指针从起点开始出发。当他们再次相遇的时候，所处位置正好是环的入口。

设C为环周长，第一次相遇，快指针已经走了，可以得到:
m+x%c = m+(2x+m)%c
进而获得:
(x+m)%c=0

所以，才会有第二阶段，让两个指针同时出发，当B指针走了m的时候，正好是环入口，也正好与A指针相遇。

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 || pHead.next.next == null) return null;
        ListNode fast = pHead.next.next;
        ListNode slow = pHead.next;
        /////先判断有没有环
        while (fast != slow) {
            if (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            } else {
                //没有环,返回
                return null;
            }
        }
        //循环出来的话就是有环，且此时fast==slow.
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我