Head also gets modified when working with LinkedList

Question

I was trying to check for palindrome Linked List, but head also gets modified and reached to end. Can someone help me why this is happening and how to resolve it?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }
        ListNode curr = head;
        ListNode prev = null;
        ListNode temp;
        while(curr != null){
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        curr = head;
        while(curr != null){
            if(prev.val != curr.val){
                return false;
            }
            curr = curr.next;
            prev = prev.next;
        }
        return true;
    }
}

I tried to create another reverse method and pass head as value but then also head is getting changed.

Answer 1

The issue you're facing is happening because the code you've written is actually modifying the original linked list when you reverse it. This means that after the reversal, the head of the linked list is now pointing to the end of the list, and you're effectively losing access to the rest of the elements.

To fix this, you should create a copy of the linked list before reversing it. You can do this by creating a new linked list and copying the values from the original list to the new one.

Solution:

class Solution {
    public boolean isPalindrome(ListNode head) {
        // Create a copy of the linked list
        ListNode copy = new ListNode(head.val);
        ListNode copyCurr = copy;
        ListNode curr = head.next;

        while (curr != null) {
            copyCurr.next = new ListNode(curr.val);
            copyCurr = copyCurr.next;
            curr = curr.next;
        }

        // Reverse the copy
        ListNode prev = null;
        ListNode temp;
        curr = copy;
        while (curr != null) {
            temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        // Compare the original and reversed linked lists
        curr = head;
        while (curr != null) {
            if (prev.val != curr.val) {
                return false;
            }
            curr = curr.next;
            prev = prev.next;
        }

        return true;
    }
}

In this code, I've added a step to create a copy of the linked list (copy) before reversing it. The copy linked list is then used for the comparison, while the original head remains intact. This should resolve the issue you were facing.