Palindrome Linked List Check

Welcome to our next lesson! In our previous sessions, we explored the fast and slow pointer pattern, culminating in a deep dive into the mathematics that makes finding a cycle's starting node possible. We saw how this technique elegantly solves problems by creating a relative difference in speed between two pointers traversing a data structure.

Today, we'll continue to build on this foundation. We're going to tackle another classic linked list problem: determining if a list is a palindrome. You'll see how the fast and slow pointer pattern can be masterfully combined with another fundamental operation—list reversal—to create an efficient solution. This is a perfect example of a problem where recognizing how to merge two known patterns is the key to an optimal approach.

The Palindrome Problem in a Linked List

A palindrome is a sequence that reads the same forwards and backwards. For an array, checking this is straightforward: you can use two pointers, one at each end, and move them inwards, comparing elements. However, with a singly linked list, you can't easily move backward from the tail.

The most direct approach might be to copy the linked list's values into an array and then apply the two-pointer check. Another common idea is to use a stack: traverse the list, push every value onto the stack, then traverse the list again, popping from the stack and comparing at each node. Both methods work, but they require $O(N)$ extra space. The real challenge, and what interviewers often look for, is a solution with $O(1)$ space complexity.

The O(1) Space Strategy: A Four-Step Process

To solve this in constant space, we need to manipulate the list in-place. The core idea is to compare the first half of the list with the reversed second half. This elegant process can be broken down into four distinct steps:

1. Find the Middle: Use the fast and slow pointer technique to locate the middle of the linked list.
2. Reverse the Second Half: Reverse the portion of the list that comes after the middle node.
3. Compare Both Halves: Iterate through the original first half and the newly reversed second half, comparing node values.
4. Restore the List: Reverse the second half again to return the linked list to its original state. This is a crucial step for clean, non-destructive code.

The following image provides a fantastic visual summary of this entire process.

Now, let's break down each step in detail.

Step 1 & 2: Find the Middle and Reverse

We've already covered finding the middle node and reversing a linked list in previous lessons, and now we get to combine them.

First, we use the standard "tortoise and hare" algorithm. Both slow and fast pointers start at the head. In each iteration, slow moves one step, and fast moves two. When fast reaches the end of the list (or null), slow will be at the middle.

• For an odd-length list (e.g., 1->2->3->2->1), slow will land on the exact middle node (3).
• For an even-length list (e.g., 1->2->2->1), slow will land on the first of the two middle nodes (the first 2).

Once we find the middle, the head of the second half is slow.next. We can then pass this node to our iterative list reversal function.

The following video from NeetCode walks through this entire process, starting with the simple array-based solution before diving into the optimal approach we're discussing.

Step 3 & 4: Compare and Restore

After reversing the second half, we have two sub-lists to compare:

• The first half, starting from head.
• The reversed second half, starting from the new head returned by our reversal function.

We can use two pointers, let's call them left (starting at head) and right (starting at the new head of the second half). We advance both pointers one step at a time, comparing their values. If we find any mismatch, we can immediately conclude the list is not a palindrome. If the right pointer reaches null without any mismatches, the list is a palindrome.

Before returning true, it's best practice to restore the list's original structure. We do this by reversing the second half one more time. This ensures that the function has no side effects on the input data structure, a quality highly valued in software engineering.

The takeuforward tutorial provides a comprehensive textual explanation of this algorithm, including the restoration step.

Handling Edge Cases

A key part of mastering any algorithm is understanding its behavior with edge cases. For this problem, the main consideration is the difference between odd and even length lists.

• Odd Length (e.g., 1->2->3->2->1): The slow pointer will stop at 3. We reverse the part starting from slow.next, which is 2->1, turning it into 1->2. We then compare 1->2 (from the head) with 1->2 (the reversed part). The middle element 3 is effectively ignored, which is correct for a palindrome check.
• Even Length (e.g., 1->2->2->1): The slow pointer stops at the first 2. We reverse the part from slow.next, which is 2->1, turning it into 1->2. We then compare 1->2 (from the head) with 1->2 (the reversed part).

The algorithm handles both cases naturally without special logic, which is a sign of its robustness. The NeetCode article below offers a very concise summary and points out some common implementation pitfalls.

Conclusion

Today, we've constructed a powerful, space-efficient solution by assembling building blocks we've studied before. This is a common theme in advanced algorithm problem-solving: recognizing that a complex problem can be decomposed into a sequence of simpler, known patterns.

Key Takeaways:

• A linked list palindrome can be checked in $O(N)$ time and $O(1)$ space.
• The solution combines three core linked list patterns: finding the middle node (fast/slow pointers), reversing a list, and iterating with two pointers.
• The four-step process is: find middle -> reverse second half -> compare halves -> restore second half.
• Restoring the list to its original state is a crucial part of writing clean, non-destructive functions.

In our next and final lesson of this module, we will see how the fast and slow pointer pattern can be generalized beyond linked lists. We'll apply the cycle detection concept to an array-based problem, showcasing the versatility of this powerful technique.