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

V2EX = way to explore

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

已注册用户请登录

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

感觉也没啥区别呀

我的代码：

public class Solution { public ListNode detectCycle(ListNode head) { i(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 的观点。