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

V2EX = way to explore

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

已注册用户请登录

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

（腾讯云最新优惠活动来了：云产品限时1折，云服务器低至88元/年，点击这里立即抢购：9i0i.cn/qcloud，更有2860元代金券免费领取，付款直接抵现金用，点击这里立即领取：9i0i.cn/qcloudquan）

（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）

感觉也没啥区别呀

我的代码：

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

208 天前

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

013231

208 天前

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