Checking if the values of a Singly Linked List form a Palindrome

Question

I'm trying to solve the following problem:

Palindrome Linked List

Given the head of a singly linked list, return true if it is a palindrome.

Input: head = [1,2,2,1]

Output: true

I'm getting a wrong result for the following test case:

[1,1,2,1]

Expected output is false, but my code returns true (screenshot)

My code:

class Solution {
    public ListNode reverseRecursive(ListNode head)
    {
        if (head == null || head.next == null)
        {
            return head;
        }
       ListNode newHead = reverseRecursive(head.next);
       head.next.next = head;
       head.next = null;

       return newHead;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode head1=reverseRecursive(head);
        
        ListNode curr = head;
        ListNode curr1 = head1;
        while (curr != null && curr1 != null)
        {
            if(curr.val == curr1.val)
            {
                curr = curr.next;
                curr1 = curr1.next;
            } else {
                return false;
            }
        }
        return true;
    }
}

I have used recursion to reverse the array and then compare the nodes of the linked list one by one, traversing through the list.

Class ListNode defined as follows:

public static class ListNode {
    int val;
    ListNode next;
    
    ListNode() {
    }
    
    ListNode(int val) {
        this.val = val;
    }
    
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

Answer 1

The logic inside isPalindrome() is correct. The issue resides in the reverseRecursive() method.

Firstly, you don't have to reverse the existing list. Secondly, this method actually doesn't reverse the list, the list gets truncated in such a way that it contains only two first nodes.

You don't need to alter the Linked List. Instead, you can generate a new Linked List, in which each node is a copy of the node from the initial list (i.e. it has the same value) and nodes are linked in reverse order. Then inside isPalindrome() we can assign the head of the newly created reversed list to the variable curr1.

Note that according to the constraints of this task it's guaranteed that there would be at least one node, hence head would never be null.

public boolean isPalindrome(ListNode head) {
    ListNode revListHead = createReversedList(head);
    
    ListNode curr = head;
    ListNode curr1 = revListHead;
    
    while (curr != null && curr1 != null) {
        if (curr.val == curr1.val) {
            curr = curr.next;
            curr1 = curr1.next;
        } else {
            return false;
        }
    }
    return true;
}

public ListNode createReversedList(ListNode head) {
    ListNode prev;
    ListNode currCopy = new ListNode(head.val);
    ListNode curr = head;

    while (curr.next != null) {
        prev = currCopy;
        curr = curr.next;
        currCopy = new ListNode(curr.val, prev);
    }
    return currCopy;
}

main()

public static void main(String[] args) {
    ListNode head = new ListNode(1);
    ListNode cur = head;
    int[] arr = {1, 2, 2, 1};
    for (int i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    System.out.println(isPalindrome(head));
    
    cur = head;
    arr = new int[]{1, 1, 2, 1};
    for (int i = 1; i < arr.length; i++) {
        cur.next = new ListNode(arr[i]);
        cur = cur.next;
    }
    System.out.println(isPalindrome(head));
}

Output:

true    // [1, 2, 2, 1]
false   // [1, 1, 2, 1]

We can also approach this problem by dumping the values of all the nodes in a Linked List into an ArrayList.

And then iterate over its indices until the middle of the list (which is sufficient), checking the corresponding values at the front and at the back of the list.

public boolean isPalindrome(ListNode head) {
    List<Integer> values = getListOfValues(head);
    int size = values.size();
    
    boolean isPalindrome = true;
    for (int i = 0; i < size / 2; i++) {
        if (!values.get(i).equals(values.get(size - 1 - i))) {
            isPalindrome = false;
            break;
        }
    }
    return isPalindrome;
}

public List<Integer> getListOfValues(ListNode head) {
    ListNode curr = head;
    List<Integer> values = new ArrayList<>();
    while (curr != null) {
        values.add(curr.val);
        curr = curr.next;
    }
    return values;
}