回文链表

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会抛出空引用异常

希望这对您有所帮助。

回文链表

Palindrome Linked List

java

reverse

palindrome

singly-linked-list