Leetcode142环形链表-II

jiezi

5 年前

给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：

 输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

 输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

你能用 O(1)（即，常量）内存解决此问题吗？

这道题是上一道题目的升级版本，要找到环的入口，又要空间复杂度是常量。我们只能通过找规律。

假像在一个环形的足球场上，有两个运动员在跑步，一快一慢，只要时间足够长，他们两个肯定会相遇。快慢指针也是一样，假如链表有环，那么指针一快一慢，肯定会相遇。

遍历链表。循环结束条件是到达链表尾部 (如果有环则用于达不到)。

相遇之后，一个指针 slow 从相遇点 C 继续走，另一个指针 start 从链表头开始走，则相遇点即为链表入口。

代码层面的话，我们就在上一道题快慢指针相遇的地方，继续到 start 指针和 slow 指针相遇的地方就是链表入口。

public class Solution {public ListNode detectCycle(ListNode head) {if (head == null || head.next == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode start = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 上道题在这里返回, 这道题继续找一下就 OK 了.
                while (start != slow) {
                    slow = slow.next;
                    start = start.next;
                }
                return slow;
            }
        }
        return null;
    }
}

题目

题解