【链表】- 环形链表 II

1. 对应力扣题目连接

环形链表 II

2. 实现思路

a. 链表图示：

在这里插入图片描述

b. 检测链表中是否存在环，即：会相交

思路：

使用 Floyd 的龟兔赛跑算法（Floyd’s Tortoise and Hare algorithm），即快慢指针法，可以有效解决此问题。

方案：

初始化两个指针，慢指针 (slow) 每次走一步，快指针 (fast) 每次走两步。
如果链表中存在环，快指针和慢指针最终会在环内相遇。
如果链表无环，快指针会先到达链表末端。如上图示。

c. 找到环的起点，即：环形入口点

思路：

因为环会相交，所有里程数一定相等，而快慢指针的速度差为2:1；
所以：快慢总的里程等式为（n代表快指针的圈数）：（x+y）* 2 = x+y + n(y+z)
推算：
x+y = n(y+z)
x = n(y+z) -y
x = (n-1)(y+z) +z
如：n=1；则 x=z

方案：

当快慢指针在环内相遇时，将其中一个指针重置到链表头部。
两个指针每次都只走一步，当它们再次相遇时，相遇的节点即为环的起点。

3. 实现案例代码

public class CircularListIiTwo {

    public static void main(String[] args) {

        // 示例链表：[3,2,0,-4]，尾部连接到索引 1
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(0);
        ListNode node3 = new ListNode(-4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node1;  // 构成环

        ListNode cycleNode = detectCycle(head);
        if (cycleNode != null) {
            System.out.println("Cycle starts at node with value: " + cycleNode.val);
        } else {
            System.out.println("No cycle");
        }
    }

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 使用快慢指针检测环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            // 快慢指针相遇，说明存在环
            if (slow == fast) {
                ListNode ptr = head;

                // 找到环的起点
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        // 无环
        return null;
    }
}

class ListNode {
    public int val;
    public ListNode next;

    ListNode() {
    }

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

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