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

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;
}

I have found the answer to this question using this algorithm that gives me the best time complexity that I can think of.

class Solution {
    public ListNode reverse(ListNode head)
    {
        ListNode prev=null;
        ListNode curr=head;
        
        while(curr != null)
        {
            ListNode next=curr.next;
            curr.next=prev;//Assigning
            
            //Updation
            
            prev=curr;
            curr=next;
        }
//         head.next=null;
//         head =prev;
        
        return prev;
        
    }
    
    public ListNode findMiddle(ListNode head)
    {
        ListNode hare=head;
        ListNode turtle=head;
        
        while(hare.next !=null && hare.next.next !=null)
        {
             hare=hare.next.next;//Increment by two
            turtle=turtle.next;//Increment by one 
        }
        return turtle;//This will be at middle by then
    }
    
    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null)
        {
            return true;
        }
        
        ListNode middle= findMiddle(head);//1st half  end
        ListNode secondHalfStart=reverse(middle.next);
        
        ListNode firstHalfStart=head;
        while(secondHalfStart != null)
        {
            if(firstHalfStart.val==secondHalfStart.val)
            {
                firstHalfStart=firstHalfStart.next;
                secondHalfStart=secondHalfStart.next;
            }else{
                return false;
            }
        }
        return true;
        
    }
}

In this, I have found the middle of the linked list using the hear and turtle approach(Floyd’s Algorithm). I have reversed the second half of the list and compared the elements one by one.