Skip to main content

234 - Palindrome Linked List

Difficulty: Easy | Pattern: Two Pointers + Reverse | Company tags: Amazon, Facebook, Apple, Google

Problem Statement​

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Follow-up: Can you do it in O(n) time and O(1) space?

Approach: Find Middle + Reverse Second Half — O(n), O(1)​

Key insight:

  1. Find the middle of the list (slow/fast pointers)
  2. Reverse the second half
  3. Compare first half with reversed second half
def isPalindrome(head) -> bool:
    # Step 1: Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse second half
    prev = None
    curr = slow
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    
    # Step 3: Compare
    left, right = head, prev
    while right:  # right is the reversed second half
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    
    return True

Algorithm Flow​

Dry Run​

head = [1,2,2,1]

Step 1 (find middle): slow=2(index 2), fast=1(end) Step 2 (reverse [2,1]): prev=1→2→None → reversed: 1→2 Step 3 (compare [1,2,2,1] with [1,2]):

  • left=1, right=1: 1==1 ✓
  • left=2, right=2: 2==2 ✓
  • right=None → stop

Return True ✓

Simpler Approach: Copy to Array — O(n), O(n)​

def isPalindrome(head) -> bool:
    vals = []
    while head:
        vals.append(head.val)
        head = head.next
    return vals == vals[::-1]

Edge Cases​

  • Single node → True
  • Two nodes: equal → True, different → False
  • Odd length: middle node is not compared (it matches itself)

Complexity​

ApproachTimeSpace
Reverse halfO(n)O(1)
Copy to arrayO(n)O(n)

Key Terms​

TermDefinition in this problem's context
Slow/fast pointersSlow moves one node at a time, fast moves two; when fast reaches the end, slow sits at the middle of the list.
In-place reversalReversing the second half by rewiring .next pointers instead of copying values, keeping space O(1).
Two-pointer comparisonAfter reversal, walking the original first half and the reversed second half together to compare values.
Mutation side-effectReversing the second half destroys the original list structure; a real interview answer should mention restoring it if required.

FAQ​

  1. Can this be solved without extra space? Yes — the find-middle + reverse-second-half approach uses O(1) extra space by reversing pointers in place, versus the O(n) array-copy approach.

  2. What happens with an odd-length list? The slow pointer lands on the middle node, which becomes the head of the reversed second half; it's compared against itself implicitly since the comparison loop only runs right (the shorter or equal-length reversed half), so the middle element is naturally skipped from mismatch checks without special-casing.

  3. Does the in-place approach mutate the input list? Yes — reversing the second half changes the list's structure permanently unless you re-reverse it back after comparison, which interviewers may ask you to add for restoring the original list.

  4. What if the list is empty or has one node? An empty list is trivially a palindrome (loop never executes, returns True); a single node has fast=head, fast.next=None immediately, so slow never advances, and reversing/comparing one node against itself returns True.

  5. What's a common follow-up interviewers ask? "Can you restore the list to its original order after checking?" — requires re-reversing the second half once comparison is done, still keeping O(1) space.

Quick Revision​

  • Pattern: slow/fast pointers to find middle, then in-place reversal, then two-pointer comparison.
  • Slow pointer advances 1 step, fast advances 2 steps — when fast hits the end, slow is at (or just past) the middle.
  • Reverse the list starting from slow using the standard three-pointer (prev, curr, next) reversal.
  • Compare head (first half) against the reversed second half node by node.
  • Stop comparison when the reversed half (right) is exhausted — this naturally skips the middle node in odd-length lists.
  • Optimal solution: O(n) time, O(1) space.
  • Simpler alternative: copy values into an array and check arr == arr[::-1] — O(n) time, O(n) space.
  • Edge cases: empty list and single node both trivially return True.
  • Trade-off to mention in interviews: in-place reversal mutates the list unless restored afterward.