Solution: Palindrome Linked List

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.

• $1\leq$ n $\leq 500$

• $0 \leq$ Node.value $\leq 9$

Solution

Since a palindrome reads the same forward and backward, an intuitive way to solve this problem is to use two pointers—one placed at the beginning and the other at the end. These pointers move toward the center, comparing the values at each step. While this approach is intuitive, it poses challenges when working with singly linked lists. Singly linked lists only have the next pointers, so moving from the end toward the center requires additional steps. To overcome this limitation, we solve this problem in three key steps: find the midpoint of the given linked list, reverse the second half, and compare both halves for symmetry. If both halves of the list match, the linked list is a palindrome. Here, reversing half the linked list allows us to use only the next pointers for comparison.

The algorithm has the following workflow:

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: