LeetCode 142环形链表II：代码无法检测环入口节点求助

你的代码存在以下几个关键问题： #

• 循环条件顺序错误：你写的hare.next!=null && hare!=null会导致空指针异常——当hare已经是null时，访问hare.next会直接报错，正确的顺序应该是先判断hare != null，再判断hare.next != null。
• detectCycle逻辑完全错误：你只让快慢指针各走了一步就判断是否相遇，这根本无法保证找到环内的相遇点；而且错误地认为相遇点的下一个节点是环入口，这不符合快慢指针找环入口的数学推导逻辑。

正确的快慢指针找环入口逻辑： #

1. 先通过快慢指针（快指针每次走2步，慢指针每次走1步）找到环内的相遇点；
2. 将其中一个指针移回链表头部，然后两个指针每次都只走1步，它们再次相遇的节点就是环的入口。

修正后的代码： #

public class Solution {
    // 辅助方法：判断是否有环，同时返回相遇节点（如果有环）
    private ListNode findMeetingNode(ListNode head) {
        ListNode hare = head;
        ListNode turtle = head;
        
        // 正确的循环条件：先判hare非空，再判hare.next非空
        while (hare != null && hare.next != null) {
            hare = hare.next.next;
            turtle = turtle.next;
            if (hare == turtle) {
                return hare; // 返回相遇节点
            }
        }
        return null; // 无环
    }
    
    public ListNode detectCycle(ListNode head) {
        ListNode meetingNode = findMeetingNode(head);
        if (meetingNode == null) {
            return null; // 无环直接返回null
        }
        
        // 将一个指针移到头部，两个指针同速前进
        ListNode ptr1 = head;
        ListNode ptr2 = meetingNode;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1; // 相遇点就是环入口
    }
}

逻辑说明： #

假设链表头部到环入口的距离为a，环入口到相遇点的距离为b，相遇点到环入口的剩余距离为c。快指针走过的路程是a + n*(b+c) + b，慢指针是a + b。因为快指针速度是慢指针的2倍，所以a + n*(b+c) + b = 2*(a + b)，化简后得到a = c + (n-1)*(b+c)，这意味着从头部和相遇点同速前进，必然会在环入口相遇。

内容的提问来源于stack exchange，提问作者Aditya Guha