educative.io

Can we do something like this instead?

Courses
,
#1

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.

#2

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