Palindrome Linked List

Question

Given a singly linked list, I want to determine if it is a palindrome. For my method, I chose to reverse the first half of the linked list and then compare if the two halves of the linked list have equivalent elements. Previously, I placed the line fast = fast.next.next at the end of the first while loop(below the 4 other lines). However, when I did that, I received a Null Pointer Exception. Now, when I shift it to the first line in the while loop, I get no errors and my program is accepted. Can someone explain to me why this is so? Thank you! Below is my code:

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

This is because if you call slow.next = prev first, you lose reference of what would be first.next.next. Why is this?

Per your initializations:

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

Now in your while loop, you are checking if fast.next is not pointing to null. Therefore, fast.next.next is valid. However, do note that slow.next is pointing to the the same reference as fast.next. For the sake of the explanation we will say that there are both pointing to a memory address called SOMETHING.

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

IF you put fast.next.next at the top of the while-loop, itis valid, because it is still pointing to something.

IF you put fast.next.next at the bottom of the while-loop, then the line slow.next = prev will first set head.next as null.

You now modified head.next to point to nothing. Because fast was pointing to the head as well, fast.next now points to null as well.

fast (head) -> next -> NULL

So calling fast.next.next will throw a null reference exception.

Hope this helps.