LeetCode.42. 环形链表 II

LeetCode.42. 环形链表 II

LeetCode.42. 环形链表 II

 

 

 一道很经典的链表题，要解决两个问题：

判断是否存在环：快慢双指针，若两个指针相遇则说明有环；找到环的入口：通过数学推导，可以发现：两个节点，分别从头结点和快慢指针相遇点开始移动，再次相遇的点就是环的入口；

数学推导：

（盗图from代码随想录）

相遇时： slow指针路程：S(slow) = x + y + n1 (y + z)fast指针路程：S(fast) = x  + n2 (y + z) + y又因为：S(slow) * 2 = S(fast) ； 所以：x = (n - 1)( y + z) + z所以，从头结点到入环口恰好等于从相遇点到入环扣的距离加上（n-1）倍环长；So两个节点，分别从头结点和快慢指针相遇点开始移动，再次相遇的点就是环的入口；

Java：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 双指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 发现环
            if (slow == fast) {
                //两个节点，分别从头结点和相遇点开始移动，再次相遇的点就是环的入口
                ListNode index1 = head;
                ListNode index2 = fast;
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

复杂度分析：

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