educative.io

Educative

Can we do something like this instead?

I’m using 2 pointers.

  1. slow - starts on the head
  2. fast - starts at the end

We link the fast node to the head node like a circular linked list.
Next,

  1. We move p1 by the next forward position

  2. We move p2 by the (n-1) forward position where n is the total length of the linked list.

  3. We check for p1.val == p2.val

  4. We check till we reach the common point (p1==p2)

    public static boolean isPalindrome(Node head) {
     int n = findListLength(head);
     Node p1 = head, p2 = head;
    
     // move p2 by (n-1) positions foreward
     while(p2.next!=null)
         p2 = p2.next;
    
     // link both the nodes
     p2.next = p1;
    
    
     while(p1!=p2) {
         p1 = p1.next;
         int pos = n-1;
         while(pos-- > 0) {
             p2 = p2.next;
         }
    
         if(p1.val != p2.val)
             return false;
     }
     return true;
    
    }
    
    public static int findListLength(Node node) {
     int c=0;
     Node curr = node;
     while(curr!=null) {
         curr = curr.next;
         ++c;
    
     }
    
     return c;
    }
    

I understand that we ended up modifying the actual linked list but just wanted to know if this can be a solution.

Hi @Debashis_Das

Thank you very much for reaching out to us. I tried to understand your logic in detail and ran it on many test cases. Following are some of my findings:

  • If the number of nodes in the LinkedList are even. It will possibly get stuck in an endless loop.
  • The time complexity of this code is less efficient ( O(N^2 ) than the provided solution for the same problem in grokking course that does the same thing in (O(N)).
  • Your code is not comparing first and last node of the LinkedList, if their values have an exact match or not. So, there is a possibility that certain inputs whose first and last nodes do not have an exact match but rest of the sequence does, will not be invalidated as a palindrome according to your code.

The last point is for a little help regarding your solution, take a third pointer (p3) and also point it to the last node of the LinkedList and once you are done with the palindrome validation just do (p3.next = null) as a second last line before “return” call to change the LinkedList from circular to normal one.

In the end, I would like to appreciate you as well for coming up with such a good logic.
Happy Coding!

1 Like