java - 回文链表

Question

给定一个单链表，我想确定它是否是回文。对于我的方法，我选择反转链表的前半部分，然后比较链表的两半是否具有相等的元素。之前，我将 fast = fast.next.next 行放在第一个 while 循环的末尾(在其他 4 行下方)。然而，当我这样做时，我收到了空指针异常。现在，当我将其移至 while 循环中的第一行时，我没有收到任何错误，并且我的程序被接受。有人可以向我解释为什么会这样吗？谢谢你!下面是我的代码:

class Solution {
    public boolean isPalindrome(ListNode head) {

        if(head == null || head.next == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;

        while(fast != null && fast.next != null){
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = temp;

        }

        if(fast != null){
            slow = slow.next;
        }

        while(prev != null && prev.val == slow.val){
            prev = prev.next;
            slow = slow.next;
        }

        return slow == null;
    }
}

Answer 1

这是因为，如果您首先调用 slow.next = prev，您就会丢失对 first.next.next 的引用。这是为什么？

根据您的初始化:

fast -> head
slow -> head
prev -> null

现在在 while 循环中，您正在检查 fast.next 是否未指向 null。因此，fast.next.next 是有效的。但是，请注意，slow.next 指向与 fast.next 相同的引用。为了便于解释，我们会说两者都指向一个名为“SOMETHING”的内存地址。

fast (HEAD) -> next -> SOMETHING
slow (HEAD) -> next -> SOMETHING

如果您将 fast.next.next 放在 while 循环的顶部，那么它是有效的，因为它仍然指向某个东西。

如果您将 fast.next.next 放在 while 循环的底部，则该行slow.next = prev 会首先将 head.next 设置为 null。

您现在将 head.next 修改为不指向任何内容。因为 fast 也指向头部，所以 fast.next 现在也指向 null。

fast (head) -> next -> NULL

因此调用fast.next.next将会抛出空引用异常。

希望这有帮助。