Search code examples
linked-listpalindrome

The question is to check whether the given linkedlist is palindrome. Please tell what am I doing wrong?

I understand other approaches such as using stack and reversing the second half of the linked list. But, what is wrong with my approach.

* 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;}
       
       while(head!=null){
           ListNode ptr=head, preptr=head;
           while(ptr.next!=null){ptr=ptr.next;}
           if(ptr==head){break;}
           while(preptr.next.next!=null){preptr=preptr.next;}
           
           if(head.val==ptr.val){
               preptr.next=null;
               head=head.next;
           }
           else{return false;}   
       }
       
       return true;
       
   }
}```
Solution

  • The following can be said about your solution:

    • It fails with an exception if head is null. To avoid that, you could just remove the first if statement. That case does not need a separate handling. When the list is a single node, then the first iteration will execute the break and so you'll get true as return value. But at least you will not access ->next when head is null

    • It mutates the given list. This is not very nice. The caller will not expect this will happen, and may need the original list for other purposes even after this call to isPalindrome.

    • It is slow. Its time complexity is quadratic. If this is part of a coding challenge, then the test data may be large, and the execution of your function may then exceed the allotted time.

    Using a stack is indeed a solution, but it feels like cheating: then you might as well convert the whole list to an array and test whether the array is a palindrome using its direct addressing capabilities.

    You can do this with just the list as follows:

    1. Count the number of nodes in the list
    2. Use that to identify the first node of the second half of the list. If the number of nodes is odd, let this be the node after the center node.
    3. Apply a list reversal algorithm on that second half. Now you have two shorter lists.
    4. Compare the values in those two lists are equal (ignore the center node if there was one). Remember the outcome (false or true)
    5. Repeat step 3 so the reversal is rolled back, and the list is back in its original state.
    6. Return the result that was found in step 4.

    This takes linear time, and so for larger lists, this should outperform your solution.