链表中环的入口结点-快慢指针-公式详解

使用快慢指针检测链表中的环和找到环的入口节点

1. 算法介绍

快慢指针算法是一种用于检测链表中是否存在环的经典算法。通过使用两个指针，一个移动速度较快，一个移动速度较慢，可以有效地检测链表中是否存在环，并在相遇时找到环的入口节点。

2. 算法实现

以下是使用 Java 实现的算法代码：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycle {
    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 entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }

        // 如果快指针或快指针的下一个为空，说明链表中不存在环
        return null;
    }
}

3. 示例说明

考虑以下链表示例：

1 -> 2 -> 3 -> 4 -> 5 -> 6
               ^         |
               |         v
               9 <- 8 <- 7

在这个示例中，节点 4 和节点 9 之间形成了一个环。我们使用上述代码进行检测，将得到环的入口节点为 4。

4. 算法原理解释

• 快慢指针同时从链表头部出发，快指针每次移动两个节点，慢指针每次移动一个节点。
• 如果链表中存在环，两个指针最终会在环内的某一点相遇。
• 一旦相遇，我们通过一个额外的指针从链表头部出发，和慢指针一样每次移动一个节点。
• 当这两个指针再次相遇时，相遇点即为环的入口节点。

让我进一步解释上述方程的含义：

在算法执行的过程中，假设链表头到环的入口点的距离为 a，相遇点到环的入口点的距离为 b，环的长度为 c。当快慢指针相遇时，慢指针走了 a + b 的距离，而快指针走了 a + b + n * c 的距离，其中 n 是快指针在环内走的圈数。

将这个信息代入方程：

2(a + b) = a + b + n·c

整理后得到：

a = (n - 1)·c + (c - b)

这个方程告诉我们，链表头到环的入口点的距离等于快指针在环内多走了 (n-1) * c 步加上慢指针在环内走的剩余距离 (c-b)。换句话说，a 的值可以表示为环的整数倍加上慢指针在环内的剩余距离。

接下来，如果我们使用一个指针从链表头开始，同时以和慢指针相同的速度前进，那么在走了 a 步之后，这个指针将会与慢指针相遇。因为两者的速度相同，它们在环内的相对位置不会发生改变。相遇点即为环的入口点。

希望这一解释能够更清晰地说明为什么在找到环后，再使用一个指针从链表头开始，最终能够在环的入口点与慢指针相遇。

5. 时间复杂度

该算法的时间复杂度为 O(n)，其中 n 是链表的长度。

6. 结论

快慢指针算法是一种高效的方法，用于检测链表中是否存在环，并找到环的入口节点。通过掌握这个算法，您可以在解决相关问题时更加灵活地使用链表数据结构。