题目分析

环形链表 II 的问题要求不仅要判断链表中是否存在环，还要找到环的起点。这个问题可以通过扩展快慢指针技术来解决。与环形链表 I 的主要区别在于，环形链表 II 需要进一步操作以找到环的入口节点。

解题思路

快慢指针技术的使用与环形链表 I 相同，但当快慢指针首次相遇时，我们将使用额外的步骤来找到环的起点。

使用快慢指针找到相遇点：快指针每次移动两步，慢指针每次移动一步。如果链表中有环，快慢指针最终会在环内的某个点相遇。
找到环的入口：当快慢指针首次相遇后，将其中一个指针（比如快指针）移回链表的起点，然后两个指针都以每次一步的速度移动。当它们再次相遇时，相遇点即为环的入口。

这种方法的原理基于数学证明，即从头节点到环入口的距离加上从相遇点到环入口的距离的倍数等于快慢指针的相遇点。

Java解法

下面是使用Java语言的解法：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (slow == fast) {
              	// 快慢指针相遇了，将快指针移回链表起点
                ListNode ptr = head;
                while (ptr != slow) {
                  	// 两个指针每次一步速度移动，再次相遇时，就是环的入口
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

时间复杂度

寻找相遇点：在快慢指针相遇之前，快指针最多会遍历整个链表一次。在最坏的情况下，这部分的时间复杂度为 O(n)，其中 n 是链表中的节点数。假设链表的非环部分长度为 L，环的长度为 C，那么在快慢指针相遇时，快指针最多走 L+C（走完非环部分进入环）+C（在环内可能多走一圈），慢指针最多走 L+C（进入环内并在某点相遇）。
找到环的入口：当快指针重新从头开始，和慢指针以相同速度移动时，它们最多会在环的入口处相遇。这部分操作在最坏情况下的时间复杂度也是 O(n)。

因此，整个算法的时间复杂度为 O(n)。

空间复杂度

这个算法主要使用了快慢指针来找到环的相遇点，以及两个指针来找到环的入口。除了存储这几个指针之外，没有使用额外的空间进行计算或存储数据结构。
因此，这个算法的空间复杂度为 O(1)，即常数空间复杂度。

References

142. 环形链表 II ↩︎

趣味算法题

快慢指针：环形链表 II

题目分析

解题思路

Java解法

References