【链表】Leetcode 142. 环形链表 II【中等】

环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

示例1:
在这里插入图片描述
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解题思路

1、使用快慢指针确定链表是否有环。
2、如果链表有环，则通过数学推导找到环的起点。
关键理解点梳理：
（1）快指针比慢指针多走了环的整数倍的距离，这是由于快慢指针的移动速度差异所导致的
在快慢指针相遇之前，快指针每次移动的步数都是慢指针的两倍。
当快慢指针进入环中后，它们在环内以不同的速度移动。
快指针每次移动两步，慢指针每次移动一步，那么在环内，快指针比慢指针每次多走一步。
如果它们能在环中相遇，快指针一定比慢指针多走了环的整数倍的距离。
f=快指针走的路程 s=慢指针走的路程 b环的路程 a入口到环的距离
f = 2s f=s+nb 得s = nb
（2）如果让指针从链表头部一直向前走并统计步数k ,而k=走到链表入口节点时的步数则k=a+nb
而目前 slow 指针走了 nb 步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口
刚好a是入口到环的距离，慢指针可以和head一起慢走，他们相遇时，
一定是都走了a，入口也就找到了

a、b 环示例图：
在这里插入图片描述

Java实现

public class LinkedListCycleII {

static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
    
    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) {
                // 有环，重新从头和相遇点开始找环的起始点
                //head节点到环入口长度为a 
                fast = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow; // 返回环的起始点
            }
        }

        // 链表中没有环
        return null;
    }

    public static void main(String[] args) {
        LinkedListCycleII solution = new LinkedListCycleII();

        // 示例：创建有环链表
        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 result = solution.detectCycle(head);

        if (result != null) {
            System.out.println("环的起始节点值为：" + result.val);
        } else {
            System.out.println("链表中无环。");
        }
    }
}