Solution: Palindrome Linked List

Let's solve the Palindrome Linked List problem using the Fast and Slow Pointers pattern.

Statement

Given the head of a linked list, your task is to check whether the linked list is a palindrome or not. Return TRUE if the linked list is a palindrome; otherwise, return FALSE.

Note: The input linked list prior to the checking process should be identical to the list after the checking process has been completed.

Constraints:

Let n be the number of nodes in a linked list.

  • 11 \leq n 500\leq 500

  • 00 \leq Node.value 9\leq 9.

Solution

The fast and slow pointers technique helps determine whether a linked list is a palindrome or not, because it allows us to efficiently traverse the list and find the middle node in a single pass. We can do this in linear time and with constant extra space.

To determine whether a linked list is a palindrome, we first find the middle node of the linked list using the fast and slow pointers approach. Then, we will reverse the second half of the linked list, starting from the node after the middle node until the end of the list. Next, we will compare the first half with the second half.

If both halves of the list match, the linked list is a palindrome. Otherwise, it is not. In the end, we reverse the second half of the linked list again. This is done to revert it to the original structure of the linked list so that the input linked list is not modified by the palindrome checking process.

The algorithm to solve this problem is as follows:

  1. First, we will find the middle node of the linked list. To do this, we’ll traverse the linked list using two pointers, where the slow pointer will move one step forward, and the fast pointer will move two steps forward. We’ll do this until the fast pointer reaches the end of the list or a null node. At this point, the slow pointer will be pointing at the middle node of the list.

  2. Next, we’ll reverse the second half of the linked list, starting from the node after the middle node. To reverse the list, we will follow these steps:

  • Initialize three pointers: prev, next, and curr. The prev and next pointers are initialized as NULL, while curr is initialized to the head of the linked list.
  • Iterate over the linked list. While iterating, perform the following steps:
    • Before changing the next of curr, store the next node using the following line of code: next = curr.next.
    • Now, we will update the next pointer of curr with the prev pointer. This will reverse the pointer of the current node from forward to backward, eventually aiding the reversal of the linked list.
    • After reversing the pointer, we will update prev as curr and curr as next, using the following lines of code respectively: prev = curr and curr = next.

Let’s look at the following illustration to get a better understanding of reversing the linked list:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.