# Can we do something like this instead?

I’m using 2 pointers.

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

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) {

// move p2 by (n-1) positions foreward
while(p2.next!=null)
p2 = p2.next;

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.

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