与Linkedlist相关的算法问题

Question

我试图从这里的单链接列表返回中间节点，这就是我的方法，但我在这里一直得到Nullpointexception。有人能解释我哪里错了吗？

* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head; 
ListNode fast = head;
if (slow == null) {
return null;
}
if (slow.next.next == null) {
return slow.next;
}
while (slow.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}

Answer 1

我相信这段代码中没有错误。

我刚刚用一个看起来像1->2->3->4->5的链表运行了您的代码，就像您在评论中所说的那样，它运行得很好。

此外，这是LeetCode的一个问题，您发布的代码通过了上面的所有测试用例。事实上，这段代码看起来与上面提供的第三个解决方案完全相同(您可以通过单击"解决方案"选项卡来查看(。

---

后期编辑：

在更新的代码中出现空指针异常的原因是，在访问fast.next.next之前，没有检查fast.next是否为空。因此，如果将while循环条件从while (slow.next != null && fast.next.next != null)更改为while (slow.next != null && fast.next != null && fast.next.next != null)，那么就可以消除空指针异常。

然而，这仍然会导致错误答案的判决，因为您的算法不正确。

您不应该检查fast.next和fast.next.next是否为非null，而应该检查fast和fast.next是否为null。我建议你把它写在纸上看看原因(你发布的1->2->3->4->5->6代码会失败，答案应该是ListNode3(。以下提供了带有这些更改的更新代码：

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