Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 36

Palindrome Linked List: From O(N) to O(1) Space

Recommended resources

Hello! In our last lesson, we mastered merging two sorted linked lists by progressing from simple to optimal pointer-based solutions. This honed our ability to manipulate next pointers to restructure a list efficiently.

Today, we'll tackle another classic problem that is a favorite in technical interviews: determining if a linked list is a palindrome. This problem is an excellent showcase of your problem-solving skills, as the optimal solution requires you to cleverly combine several linked list patterns we've previously discussed.

Our goal is to implement a function that checks for this property, and in line with your learning preference, we will start with a straightforward O(n) space solution before building up to the highly efficient O(1) space solution expected in top-tier company interviews.

This image shows the problem statement for "Palindrome Linked List." A palindrome is a sequence that reads the same forwards and backward. The examples illustrate a palindromic list (1 -> 2 -> 2 -> 1) and a non-palindromic one (1 -> 2).

1. Brute-Force Approach: Using a Stack (O(n) Space)

The definition of a palindrome is that a sequence is the same forwards and backward. For a linked list, which we can only traverse forward, how can we check the "backward" sequence? The most intuitive way is to store the node values in a data structure that allows us to retrieve them in reverse order. A stack, with its Last-In, First-Out (LIFO) behavior, is perfectly suited for this.

The algorithm is straightforward:

  1. First Pass: Traverse the entire linked list from head to tail. For each node you visit, push its value onto a stack.
  2. Second Pass: Reset a pointer back to the head of the list. Traverse the list again.
  3. Comparison: For each node in the second traversal, pop an element from the stack and compare it with the current node's value.
    • If the values do not match at any point, the list is not a palindrome, and we can immediately return false.
    • If we complete the second traversal and all values have matched, the list is a palindrome, and we return true.

The following video from the takeUforward channel provides an excellent explanation of this stack-based approach.

L10. Check if a LinkedList is Palindrome or Not | Multiple Approaches

This segment explains the problem and details the brute-force solution using a stack. Pay close attention to how the LIFO property of the stack is used to simulate a reverse traversal for comparison.

Watch from the explanation of the naive solution. Striver covers the logic, pseudocode, and a complexity analysis.

To see how this translates into Java, you can review the implementation in the GeeksforGeeks article.

Palindrome Linked List

This article section outlines the stack-based approach and provides a clean Java implementation.

Read the section titled Steps to solve the problem and then study the corresponding Java code. Notice how it directly implements the two-pass algorithm we discussed.

This method is correct and easy to understand, but it has a significant drawback.

  • Time Complexity: O(n) + O(n) = O(n). We traverse the list twice.
  • Space Complexity: O(n). The stack needs to store all n elements of the linked list.

In an interview, after presenting this solution, you would almost certainly be asked: "Can you do it with O(1) space?" This leads us to the optimal approach.

2. Optimal Approach: In-Place Reversal (O(1) Space)

To solve this problem without significant extra space, we must manipulate the list's pointers. The core insight is to compare the first half of the list with a reversed version of the second half. If they are identical, the list is a palindrome.

This elegant solution is a three-step process that combines patterns we've already mastered:

  1. Find the Middle of the List: Using the slow and fast pointer technique, we can find the middle node. The slow pointer will end up at the node marking the end of the first half.
  2. Reverse the Second Half: Starting from the node after the middle (slow.next), we perform an in-place reversal of the rest of the list. You'll recall this iterative reversal from a previous lesson.
  3. Compare the Halves: We now have two pointers: one at the original head (start of the first half) and one at the newHead of the reversed second half. We can iterate through both halves simultaneously, comparing node values.
    • If we find a mismatch, we know it's not a palindrome.
    • If we traverse the entire second half without a mismatch, the list is a palindrome.

A crucial final step for a production-quality solution is to restore the list by reversing the second half again, returning the linked list to its original structure.

This diagram illustrates the state of the list just before the comparison step. The first half is intact, while the second half has been reversed.

After finding the middle node (`slow`) and reversing the subsequent nodes, we are set up for comparison. One pointer starts at the `head`, and another starts at the head of the reversed second half (`prev`), moving towards each other conceptually.

Striver's video provides a fantastic walkthrough of this entire process, including handling edge cases for odd and even length lists.

L10. Check if a LinkedList is Palindrome or Not | Multiple Approaches

This video covers the optimal O(1) space solution. It breaks the problem down into the three key steps: finding the middle, reversing the second half, and comparing. The complexity analysis is also covered.

Watch from the optimized approach section. Pay special attention to the logic for finding the middle (middle finding code), the reversal, the comparison, and the final step of restoring the list (re-reversing).

For a complete Java implementation, the takeUforward article provides clear and well-commented code.

Check if the given Linked List is Palindrome - Tutorial

This article details the optimal algorithm, breaking it down into finding the middle, reversing, comparing, and restoring the list.

Read the Algorithm steps. Then, carefully study the full Java code. Notice how it uses a helper function for reversing the list, which is clean design. The code also correctly handles restoring the list's original structure.

This approach is highly efficient and demonstrates a strong command of linked list manipulations.

  • Time Complexity: O(n/2) for finding the middle + O(n/2) for reversing + O(n/2) for comparing + O(n/2) to restore = O(n).
  • Space Complexity: O(1). We only use a few pointers, regardless of the list size.

Practice Problem

You are now well-equipped to solve this problem on LeetCode. Try to implement both the stack-based solution and the optimal O(1) space solution to solidify your understanding of the trade-offs.

Conclusion

In this lesson, we tackled the palindrome linked list problem by progressing from an intuitive but space-inefficient solution to a clever and optimal one.

Key Takeaways:

  • Brute-Force (O(n) space): Using a Stack provides a simple two-pass solution by leveraging its LIFO property to compare the list with its reverse.
  • Optimal (O(1) space): The interview-standard solution involves a multi-step, in-place manipulation:
    1. Find the middle with slow-fast pointers.
    2. Reverse the second half of the list.
    3. Compare the first half with the reversed second half.
    4. (Optional but recommended) Restore the original list structure.
  • This problem beautifully illustrates how combining fundamental patterns (like list traversal, reversal, and multi-pointer techniques) can lead to highly efficient algorithms.

In our next lesson, we will push our pointer manipulation skills even further by tackling another advanced problem: reversing the nodes of a linked list in groups of size K.