Although this is marked as an ‘easy’ challenge, and it can indeed be solved easily and intuitively with the help of a Stack. However, a stack solution would require O(n) extra space. The difficulty can level up if we are required to solve the problem with O(1) space. We can do this with a pair of slow and fast pointers.
Before we can use either stack or two pointers to solve the problem, we have to find the middle of the Linked List first. This is decided by the nature of a palindrome: the left and right sides of the middle of the palindrome are mirroring each other.
One common technique to find the center of a Linked List is using a slow pointer and a fast pointer. Pseudo code:
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
When the loop breaks, slow is pointing at:
– the center node, if the list has an odd number of nodes;
– the first node of the second half, if the list has an even number of nodes;
But can we tell whether the list contains an odd or an even number of nodes?
The answer is YES. We can simply determine it by checking the ‘fast’ pointer:
The number of the list nodes is:
– odd, if fast.next is null;
– even, if fast is null;
With this technique, we can solve a lot of Linked List problems that require us finding the center of the list with at least one less pass.
Click here to see the original leetcode challenge.