142. 环形链表 II 我这么写为什么有个 case 无法通过

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 417 天前的主题，其中的信息可能已经有所发展或是发生改变。

感觉也没啥区别呀

我的代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != slow){
            if(fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while( fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

无法通过的 case:

输入
[3,2,0,-4]
1
输出
tail connects to node index 0
预期结果
tail connects to node index 1

可以通过的代码：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) break;
         }
        fast = head;
        while( fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

2 条回复 • 2023-10-08 11:51:36 +08:00

j1132888093

2023-10-08 11:40:58 +08:00

你这么写条件的话，把 while 改成 do while

013231

2023-10-08 11:51:36 +08:00

你的问题出在第一个循环条件的判断上。
在你的代码中，你在使用“快慢指针法”寻找环的时候，你的循环条件为 while(fast != slow)，意味着只有当 fast 和 slow 指针相等时才跳出循环。然而，这在 fast 和 slow 指针第一次初始化时就已经满足，因此你的循环根本没有执行。这导致你在后面的代码中错误地认为 fast 和 slow 指针已经找到环，并试图从头开始寻找环的入口，结果找到的是链表的头部，因为 fast 和 slow 指针都没有移动过。
================================
上面的话是 GPT 4 说的。我支持 GPT 的观点。