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

CodePudding user response：

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

CodePudding user response：

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.