Data Structures & AlgorithmsCommon Linked List Patterns & Problem Types

Common Linked List Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Linked List Patterns & Problem Types

5 / 5

Palindrome Detection

The Synthesis Problem

A palindrome is a sequence that reads the same forwards and backwards: "racecar", "level", or the list 1 → 2 → 3 → 2 → 1. Detecting palindromes in linked lists is a beautiful synthesis problem—it draws on nearly every technique we've learned: finding the middle, reversing a list, two-pointer comparison, and handling edge cases.

What makes this problem elegant is that a naïve solution is obvious (copy to array, check if array equals its reverse), but achieving O(1) space requires cleverly combining linked list operations. The optimal solution is a masterclass in pointer manipulation.

This is the culminating problem of our module on linked list patterns. By the end, you'll see how individual techniques compose into sophisticated solutions.

What You Will Learn

By the end of this page, you will: (1) Understand multiple approaches to palindrome detection, (2) Master the O(1) space solution using in-place reversal, (3) Handle both odd and even length lists, (4) Optionally restore the list to its original structure, (5) See how individual techniques synthesize into elegant solutions.

The Problem Statement

Problem:

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

Examples:

1 → 2 → 2 → 1       → true  (even length palindrome)
1 → 2 → 3 → 2 → 1   → true  (odd length palindrome)
1 → 2 → 3 → 4 → 5   → false (not a palindrome)
1                    → true  (single element)
(empty)              → true  (vacuously true)

Constraints:

O(n) time complexity required
O(1) space complexity desired (challenge mode)
The list is singly linked (no prev pointer)

Solution Approaches Overview
Approach	Time	Space	Modifies List?
Copy to array, compare	O(n)	O(n)	No
Recursive comparison	O(n)	O(n) stack	No
Reverse second half	O(n)	O(1)	Yes (restorable)

The Challenge:

With arrays, palindrome detection is trivial: compare a[i] with a[n-1-i]. But linked lists don't support random access. We can't jump to the end and compare backwards.

The clever insight: if we reverse half the list, we can then walk both halves simultaneously, comparing element by element. But which half? And how do we find where to split?

Approach 1: Copy to Array — The Baseline

The simplest approach leverages random access: copy all values to an array, then check if the array is a palindrome. This is O(n) time and O(n) space—acceptable but not optimal.

Why start here?

This establishes correctness. We can test our optimal solution against this baseline. Never skip the simple solution when debugging.

palindrome_array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def is_palindrome_array(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome using array copy.
    
    Time Complexity: O(n) - traverse once to copy, O(n) to check
    Space Complexity: O(n) - stores all values
    
    Simple and correct, but not space-optimal.
    """
    # Copy values to array
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
    
    # Check if array is palindrome
    # Compare values[i] with values[n-1-i]
    left = 0
    right = len(values) - 1
    
    while left < right:
        if values[left] != values[right]:
            return False
        left += 1
        right -= 1
    
    return True
 
 
def is_palindrome_array_pythonic(head: ListNode) -> bool:
    """Even simpler: use Python slice comparison."""
    values = []
    while head:
        values.append(head.val)
        head = head.next
    
    return values == values[::-1]

When to Use This Approach

Use the array approach when: (1) Space isn't a concern, (2) You need a quick correct solution, (3) You can't modify the original list, (4) Debugging a more complex solution. In interviews, mention this as a baseline before optimizing.

Approach 2: Recursive with Back-Pointer

An elegant recursive approach uses the call stack to 'remember' the front of the list while recursing to the back. During unwinding, we compare front and back simultaneously.

The Insight:

Recursion naturally reaches the end first. If we maintain a pointer to the front that advances after each comparison, we can match front and back as the recursion unwinds.

Caveat:

This is O(n) space due to the call stack—not truly space-optimal, but elegant and instructive.

palindrome_recursive.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def is_palindrome_recursive(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome using recursion.
    
    Time Complexity: O(n) - visit each node once
    Space Complexity: O(n) - recursion stack depth
    
    The front pointer advances as we unwind from the back.
    """
    # Use a mutable container to track front pointer across recursive calls
    front = [head]  # List acts as mutable reference
    
    def check(node: ListNode) -> bool:
        """
        Recurse to end, then compare as we unwind.
        Returns False immediately if mismatch found.
        """
        if node is None:
            return True
        
        # Recurse to the end first
        if not check(node.next):
            return False  # Early termination if mismatch found
        
        # Now unwinding: compare front with current (back)
        if front[0].val != node.val:
            return False
        
        # Advance front for the next comparison
        front[0] = front[0].next
        
        return True
    
    return check(head)
 
 
def is_palindrome_recursive_traced(head: ListNode) -> bool:
    """Same algorithm with tracing to visualize the recursion."""
    front = [head]
    
    def check(node: ListNode, depth: int = 0) -> bool:
        indent = "  " * depth
        node_val = node.val if node else "null"
        print(f"{indent}check({node_val})")
        
        if node is None:
            print(f"{indent}  Base case: return True")
            return True
        
        print(f"{indent}  Recursing...")
        if not check(node.next, depth + 1):
            print(f"{indent}  Mismatch propagated up, return False")
            return False
        
        front_val = front[0].val
        print(f"{indent}  Unwinding: compare front={front_val} with back={node.val}")
        
        if front_val != node.val:
            print(f"{indent}  Mismatch! return False")
            return False
        
        front[0] = front[0].next
        print(f"{indent}  Match! advance front, return True")
        return True
    
    return check(head)

Trace for 1 → 2 → 2 → 1:

check(1)        front = 1
  check(2)      front = 1
    check(2)    front = 1
      check(1)  front = 1
        check(null) → True
      Unwind: compare front[1] with back[1] → match, front = 2
    Unwind: compare front[2] with back[2] → match, front = 2
  Unwind: compare front[2] with back[2] → match, front = 1
Unwind: compare front[1] with back[1] → match, front = null
Result: True

Stack Space Consideration

While elegant, this approach uses O(n) stack space. For a list with 1 million nodes, that's 1 million stack frames—potentially causing stack overflow. The following O(1) space solution avoids this.

Approach 3: The O(1) Space Strategy

The optimal O(1) space solution combines three techniques:

Step 1: Find the Middle

Use slow/fast pointers. When fast reaches the end, slow is at the middle.

Step 2: Reverse the Second Half

Reverse the list from the middle to the end in-place.

Step 3: Compare First and Reversed Second Half

Walk both halves simultaneously, comparing values.

Step 4 (Optional): Restore the List

Reverse the second half again to restore the original structure.

Visual Intuition

Imagine folding a piece of paper with the list written on it. A palindrome would have matching characters at each fold point. By reversing the second half, we make it easy to walk both halves in the same direction, comparing element by element.

Handling Odd vs Even Length:

Even length: 1 → 2 → 2 → 1

Middle is between the two 2s
First half: 1 → 2
Second half reversed: 1 → 2
Compare: (1,1) ✓ (2,2) ✓ → palindrome

Odd length: 1 → 2 → 3 → 2 → 1

Middle is 3
First half: 1 → 2 → 3
Second half reversed: 1 → 2
We skip the middle during comparison (it matches itself)
Compare: (1,1) ✓ (2,2) ✓ → palindrome

The key is how we define "middle" and where we start the second half.

List Structure After Each Step
Length	Original	After Finding Middle	After Reversing
Even (4)	1→2→2→1	slow at 2nd '2'	1→2 1→2 (reversed second half)
Odd (5)	1→2→3→2→1	slow at '3'	1→2→3 1→2 (reversed, 3 is shared)

Optimal Implementation

palindrome_optimal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
def is_palindrome(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome in O(1) space.
    
    Time Complexity: O(n) - multiple passes but each is O(n)
    Space Complexity: O(1) - only uses pointers
    
    Strategy:
    1. Find middle using slow/fast pointers
    2. Reverse the second half
    3. Compare first and second half
    4. (Optional) Restore the list
    """
    if not head or not head.next:
        return True  # Empty or single-node lists are palindromes
    
    # Step 1: Find the middle
    # For even length, slow ends at first of middle two
    # For odd length, slow ends at the true middle
    slow = head
    fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 'slow' is now at the middle (or just before for even length)
    
    # Step 2: Reverse the second half
    # Start reversing from slow.next
    second_half = reverse_list(slow.next)
    
    # Step 3: Compare the two halves
    first_half = head
    second_half_copy = second_half  # Save for restoration
    
    is_palindrome_result = True
    while second_half:
        if first_half.val != second_half.val:
            is_palindrome_result = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Step 4 (Optional): Restore the list
    slow.next = reverse_list(second_half_copy)
    
    return is_palindrome_result
 
 
def reverse_list(head: ListNode) -> ListNode:
    """
    Reverse a linked list in-place.
    Standard three-pointer technique.
    """
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    return prev
 
 
def is_palindrome_no_restore(head: ListNode) -> bool:
    """
    Same algorithm without restoration (if modification is acceptable).
    Slightly simpler, often acceptable for interview problems.
    """
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second = reverse_list(slow.next)
    
    # Compare
    first = head
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next
    
    return True

The Restoration Step

Restoring the list is often optional in interview settings, but important in production code where the caller expects the list to remain unchanged. It's a single additional reversal—O(n) time, O(1) space—and demonstrates attention to side effects.

Deep Dive: Finding the Middle Correctly

The middle-finding step is subtle. Different loop conditions give slightly different results:

Condition 1: while fast and fast.next

Even [1,2,3,4]: slow ends at 3 (second middle)
Odd [1,2,3,4,5]: slow ends at 3 (true middle)

Condition 2: while fast.next and fast.next.next

Even [1,2,3,4]: slow ends at 2 (first middle)
Odd [1,2,3,4,5]: slow ends at 3 (true middle)

For palindrome detection, we want to reverse starting from slow.next. Both conditions work, but condition 2 gives us a cleaner split for even-length lists.

Slow Pointer Position by Condition
List	Condition 1 (fast and fast.next)	Condition 2 (fast.next and fast.next.next)
[1]	1	1
[1,2]	2	1
[1,2,3]	2	2
[1,2,3,4]	3	2
[1,2,3,4,5]	3	3
[1,2,3,4,5,6]	4	3

Why Condition 2 is Preferred:

We reverse everything after slow. For even lists like [1,2,2,1]:

Condition 1: slow at second '2'. Reverse [1]. Compare [1,2,2] with [1]. Not symmetric.
Condition 2: slow at first '2'. Reverse [2,1] → [1,2]. Compare [1,2] with [1,2]. Perfect.

Condition 2 ensures the first half has length ⌈n/2⌉ and the reversed second half has length ⌊n/2⌋. The comparison naturally skips the middle element for odd-length lists.

Trace Carefully

When debugging middle-finding, trace through specific examples: [1,2], [1,2,3], [1,2,3,4]. Verify slow is where you expect after the loop. Off-by-one errors here cause subtle bugs that are hard to diagnose.

Edge Cases

Let's verify our solution handles all edge cases:

Edge Case 1: Empty List

Input: None
Output: True (vacuously a palindrome)

Edge Case 2: Single Node

Input: [1]
Output: True

Edge Case 3: Two Nodes, Same Value

Input: [1, 1]
Output: True

Edge Case 4: Two Nodes, Different Values

Input: [1, 2]
Output: False

Edge Case 5: Even Length Palindrome

Input: [1, 2, 2, 1]
Output: True

Edge Case 6: Odd Length Palindrome

Input: [1, 2, 3, 2, 1]
Output: True

Edge Case 7: Odd Length Non-Palindrome

Input: [1, 2, 3, 4, 5]
Output: False

palindrome_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def test_palindrome_edge_cases():
    """Comprehensive edge case testing."""
    
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        curr = head
        for val in values[1:]:
            curr.next = ListNode(val)
            curr = curr.next
        return head
    
    # Test empty list
    assert is_palindrome(None) == True, "Empty list failed"
    
    # Test single node
    assert is_palindrome(create_list([1])) == True, "Single node failed"
    
    # Test two nodes, same
    assert is_palindrome(create_list([1, 1])) == True, "Two same failed"
    
    # Test two nodes, different
    assert is_palindrome(create_list([1, 2])) == False, "Two different failed"
    
    # Test even palindrome
    assert is_palindrome(create_list([1, 2, 2, 1])) == True, "Even palindrome failed"
    
    # Test odd palindrome
    assert is_palindrome(create_list([1, 2, 3, 2, 1])) == True, "Odd palindrome failed"
    
    # Test even non-palindrome
    assert is_palindrome(create_list([1, 2, 3, 4])) == False, "Even non-palindrome failed"
    
    # Test odd non-palindrome
    assert is_palindrome(create_list([1, 2, 3, 4, 5])) == False, "Odd non-palindrome failed"
    
    # Test longer palindrome
    assert is_palindrome(create_list([1,2,3,4,5,4,3,2,1])) == True, "Long palindrome failed"
    
    # Test almost palindrome
    assert is_palindrome(create_list([1,2,3,4,5,5,3,2,1])) == False, "Almost palindrome failed"
    
    print("All palindrome tests passed! ✓")

Common Mistakes and How to Avoid Them

Classic Mistakes in Palindrome Detection

•Wrong slow/fast condition — Using while fast and fast.next vs while fast.next and fast.next.next gives different middle positions. Trace through examples to verify.
•Not handling empty/single-node lists — These are valid palindromes but might cause null pointer errors without explicit checks.
•Comparing wrong halves — After reversing, make sure you're comparing first_half (from head) with second_half (reversed), not mixing them up.
•Forgetting to save second_half_copy — If you restore the list, you need the original start of the reversed half, not the traversed-to-end pointer.
•Not stopping at the right time — Compare while second_half is not null. The first half might be longer (odd-length case), but that's okay.
•Breaking on any false without returning — If you find a mismatch, set a flag but continue to restore if needed, OR return immediately if no restoration required.

The Early Return Trap

If you plan to restore the list (Step 4), don't return False immediately upon mismatch. Set a flag, finish comparison, restore the list, then return the flag. Returning early leaves the list in a modified state.

Complexity Analysis

Time Complexity: O(n)

Finding middle: O(n/2) — fast traverses whole list
Reversing second half: O(n/2) — half the nodes
Comparing halves: O(n/2) — iterate through half
Optional restoration: O(n/2) — reverse again

Total: O(n/2) + O(n/2) + O(n/2) + O(n/2) = O(2n) = O(n)

Space Complexity: O(1)

A fixed number of pointers: slow, fast, first_half, second_half, prev, curr, next_temp
No data structures that grow with input size
No recursion (unlike the recursive approach)

Why This is Optimal:

We must examine every element to verify palindrome: Ω(n) lower bound
We achieve Θ(n) time with O(1) space—optimal on both fronts

Approach Comparison
Approach	Time	Space	Trade-off
Array copy	O(n)	O(n)	Simple, inefficient space
Recursion	O(n)	O(n) stack	Elegant, stack overflow risk
Reverse half	O(n)	O(1)	Optimal, modifies list temporarily

Synthesis: How Patterns Combine

Palindrome detection is a synthesis problem that draws on multiple patterns we've studied:

Pattern 1: Two-Pointer (Slow/Fast)

Used to find the middle without knowing the length. This appears in:

Finding the middle of a list
Cycle detection (Floyd's algorithm)
Finding kth from end

Pattern 2: List Reversal

Used to enable backwards traversal on a forward-only structure. This appears in:

Reversing a full list
Partial reversal (reverse between positions)
Reordering lists

Pattern 3: Pointer Comparison Walk

Used to compare two lists element by element. This appears in:

Merging sorted lists
Checking list equality
Intersection detection

Problems That Use Similar Synthesis

•Reorder List — Find middle, reverse second half, interleave
•Sort List — Find middle, recursively sort halves, merge
•Rotate List — Find length, find new tail, relink
•Split List in Parts — Calculate part sizes, traverse and sever
•Add Two Numbers II — Reverse, add digit by digit, reverse result

Building Your Toolkit

The power of pattern mastery is composition. Once you can find middles, reverse lists, and compare segments fluently, problems like palindrome detection become obvious assemblies of known techniques. Focus on mastering the primitives; the combinations follow naturally.

Summary: Mastering Palindrome Detection

Palindrome detection synthesizes the core linked list patterns into an elegant solution. Let's consolidate the key insights:

Key Takeaways

•The O(1) space solution combines middle-finding (slow/fast) + reversal + comparison—three patterns in one solution.
•Choose the right middle-finding condition — while fast.next and fast.next.next gives the split point we need.
•Reversing the second half enables element-by-element comparison without random access or extra space.
•Restoration is optional but important in production code to avoid modifying the caller's data.
•Edge cases (empty list, single node, two nodes) require explicit handling or careful design.
•This problem is a pattern composition — master the primitives and combinations become natural.

Module Complete:

You've now mastered the five essential linked list patterns that appear repeatedly across problems:

Reversing — Transform traversal direction
Merging — Combine sorted sequences
Nth from End — Use gaps between pointers
Partitioning — Separate by condition
Palindrome Detection — Synthesize all of the above

These patterns form a comprehensive toolkit for linked list problems. With practice, you'll recognize which patterns apply to new problems almost instantly.

Module Complete

Congratulations! You've completed the Common Linked List Patterns module. You've mastered reversal, merging, nth-from-end, partitioning, and palindrome detection—the core patterns that power linked list problem-solving. These techniques will serve you in interviews, competitive programming, and production systems alike.

5 / 5

Loading learning content...

Data Structures & AlgorithmsCommon Linked List Patterns & Problem Types

Common Linked List Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Linked List Patterns & Problem Types

5 / 5

Palindrome Detection

The Synthesis Problem

This is the culminating problem of our module on linked list patterns. By the end, you'll see how individual techniques compose into sophisticated solutions.

What You Will Learn

The Problem Statement

Problem:

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

Examples:

1 → 2 → 2 → 1       → true  (even length palindrome)
1 → 2 → 3 → 2 → 1   → true  (odd length palindrome)
1 → 2 → 3 → 4 → 5   → false (not a palindrome)
1                    → true  (single element)
(empty)              → true  (vacuously true)

Constraints:

O(n) time complexity required
O(1) space complexity desired (challenge mode)
The list is singly linked (no prev pointer)

Solution Approaches Overview
Approach	Time	Space	Modifies List?
Copy to array, compare	O(n)	O(n)	No
Recursive comparison	O(n)	O(n) stack	No
Reverse second half	O(n)	O(1)	Yes (restorable)

The Challenge:

With arrays, palindrome detection is trivial: compare a[i] with a[n-1-i]. But linked lists don't support random access. We can't jump to the end and compare backwards.

The clever insight: if we reverse half the list, we can then walk both halves simultaneously, comparing element by element. But which half? And how do we find where to split?

Approach 1: Copy to Array — The Baseline

The simplest approach leverages random access: copy all values to an array, then check if the array is a palindrome. This is O(n) time and O(n) space—acceptable but not optimal.

Why start here?

This establishes correctness. We can test our optimal solution against this baseline. Never skip the simple solution when debugging.

palindrome_array.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def is_palindrome_array(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome using array copy.
    
    Time Complexity: O(n) - traverse once to copy, O(n) to check
    Space Complexity: O(n) - stores all values
    
    Simple and correct, but not space-optimal.
    """
    # Copy values to array
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
    
    # Check if array is palindrome
    # Compare values[i] with values[n-1-i]
    left = 0
    right = len(values) - 1
    
    while left < right:
        if values[left] != values[right]:
            return False
        left += 1
        right -= 1
    
    return True
 
 
def is_palindrome_array_pythonic(head: ListNode) -> bool:
    """Even simpler: use Python slice comparison."""
    values = []
    while head:
        values.append(head.val)
        head = head.next
    
    return values == values[::-1]

When to Use This Approach

Approach 2: Recursive with Back-Pointer

An elegant recursive approach uses the call stack to 'remember' the front of the list while recursing to the back. During unwinding, we compare front and back simultaneously.

The Insight:

Recursion naturally reaches the end first. If we maintain a pointer to the front that advances after each comparison, we can match front and back as the recursion unwinds.

Caveat:

This is O(n) space due to the call stack—not truly space-optimal, but elegant and instructive.

palindrome_recursive.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def is_palindrome_recursive(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome using recursion.
    
    Time Complexity: O(n) - visit each node once
    Space Complexity: O(n) - recursion stack depth
    
    The front pointer advances as we unwind from the back.
    """
    # Use a mutable container to track front pointer across recursive calls
    front = [head]  # List acts as mutable reference
    
    def check(node: ListNode) -> bool:
        """
        Recurse to end, then compare as we unwind.
        Returns False immediately if mismatch found.
        """
        if node is None:
            return True
        
        # Recurse to the end first
        if not check(node.next):
            return False  # Early termination if mismatch found
        
        # Now unwinding: compare front with current (back)
        if front[0].val != node.val:
            return False
        
        # Advance front for the next comparison
        front[0] = front[0].next
        
        return True
    
    return check(head)
 
 
def is_palindrome_recursive_traced(head: ListNode) -> bool:
    """Same algorithm with tracing to visualize the recursion."""
    front = [head]
    
    def check(node: ListNode, depth: int = 0) -> bool:
        indent = "  " * depth
        node_val = node.val if node else "null"
        print(f"{indent}check({node_val})")
        
        if node is None:
            print(f"{indent}  Base case: return True")
            return True
        
        print(f"{indent}  Recursing...")
        if not check(node.next, depth + 1):
            print(f"{indent}  Mismatch propagated up, return False")
            return False
        
        front_val = front[0].val
        print(f"{indent}  Unwinding: compare front={front_val} with back={node.val}")
        
        if front_val != node.val:
            print(f"{indent}  Mismatch! return False")
            return False
        
        front[0] = front[0].next
        print(f"{indent}  Match! advance front, return True")
        return True
    
    return check(head)

Trace for 1 → 2 → 2 → 1:

check(1)        front = 1
  check(2)      front = 1
    check(2)    front = 1
      check(1)  front = 1
        check(null) → True
      Unwind: compare front[1] with back[1] → match, front = 2
    Unwind: compare front[2] with back[2] → match, front = 2
  Unwind: compare front[2] with back[2] → match, front = 1
Unwind: compare front[1] with back[1] → match, front = null
Result: True

Stack Space Consideration

While elegant, this approach uses O(n) stack space. For a list with 1 million nodes, that's 1 million stack frames—potentially causing stack overflow. The following O(1) space solution avoids this.

Approach 3: The O(1) Space Strategy

The optimal O(1) space solution combines three techniques:

Step 1: Find the Middle

Use slow/fast pointers. When fast reaches the end, slow is at the middle.

Step 2: Reverse the Second Half

Reverse the list from the middle to the end in-place.

Step 3: Compare First and Reversed Second Half

Walk both halves simultaneously, comparing values.

Step 4 (Optional): Restore the List

Reverse the second half again to restore the original structure.

Visual Intuition

Handling Odd vs Even Length:

Even length: 1 → 2 → 2 → 1

Middle is between the two 2s
First half: 1 → 2
Second half reversed: 1 → 2
Compare: (1,1) ✓ (2,2) ✓ → palindrome

Odd length: 1 → 2 → 3 → 2 → 1

Middle is 3
First half: 1 → 2 → 3
Second half reversed: 1 → 2
We skip the middle during comparison (it matches itself)
Compare: (1,1) ✓ (2,2) ✓ → palindrome

The key is how we define "middle" and where we start the second half.

List Structure After Each Step
Length	Original	After Finding Middle	After Reversing
Even (4)	1→2→2→1	slow at 2nd '2'	1→2 1→2 (reversed second half)
Odd (5)	1→2→3→2→1	slow at '3'	1→2→3 1→2 (reversed, 3 is shared)

Optimal Implementation

palindrome_optimal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
def is_palindrome(head: ListNode) -> bool:
    """
    Check if linked list is a palindrome in O(1) space.
    
    Time Complexity: O(n) - multiple passes but each is O(n)
    Space Complexity: O(1) - only uses pointers
    
    Strategy:
    1. Find middle using slow/fast pointers
    2. Reverse the second half
    3. Compare first and second half
    4. (Optional) Restore the list
    """
    if not head or not head.next:
        return True  # Empty or single-node lists are palindromes
    
    # Step 1: Find the middle
    # For even length, slow ends at first of middle two
    # For odd length, slow ends at the true middle
    slow = head
    fast = head
    
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # 'slow' is now at the middle (or just before for even length)
    
    # Step 2: Reverse the second half
    # Start reversing from slow.next
    second_half = reverse_list(slow.next)
    
    # Step 3: Compare the two halves
    first_half = head
    second_half_copy = second_half  # Save for restoration
    
    is_palindrome_result = True
    while second_half:
        if first_half.val != second_half.val:
            is_palindrome_result = False
            break
        first_half = first_half.next
        second_half = second_half.next
    
    # Step 4 (Optional): Restore the list
    slow.next = reverse_list(second_half_copy)
    
    return is_palindrome_result
 
 
def reverse_list(head: ListNode) -> ListNode:
    """
    Reverse a linked list in-place.
    Standard three-pointer technique.
    """
    prev = None
    curr = head
    
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    return prev
 
 
def is_palindrome_no_restore(head: ListNode) -> bool:
    """
    Same algorithm without restoration (if modification is acceptable).
    Slightly simpler, often acceptable for interview problems.
    """
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    second = reverse_list(slow.next)
    
    # Compare
    first = head
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next
    
    return True

The Restoration Step

Deep Dive: Finding the Middle Correctly

The middle-finding step is subtle. Different loop conditions give slightly different results:

Condition 1: while fast and fast.next

Even [1,2,3,4]: slow ends at 3 (second middle)
Odd [1,2,3,4,5]: slow ends at 3 (true middle)

Condition 2: while fast.next and fast.next.next

Even [1,2,3,4]: slow ends at 2 (first middle)
Odd [1,2,3,4,5]: slow ends at 3 (true middle)

For palindrome detection, we want to reverse starting from slow.next. Both conditions work, but condition 2 gives us a cleaner split for even-length lists.

Slow Pointer Position by Condition
List	Condition 1 (fast and fast.next)	Condition 2 (fast.next and fast.next.next)
[1]	1	1
[1,2]	2	1
[1,2,3]	2	2
[1,2,3,4]	3	2
[1,2,3,4,5]	3	3
[1,2,3,4,5,6]	4	3

Why Condition 2 is Preferred:

We reverse everything after slow. For even lists like [1,2,2,1]:

Condition 1: slow at second '2'. Reverse [1]. Compare [1,2,2] with [1]. Not symmetric.
Condition 2: slow at first '2'. Reverse [2,1] → [1,2]. Compare [1,2] with [1,2]. Perfect.

Condition 2 ensures the first half has length ⌈n/2⌉ and the reversed second half has length ⌊n/2⌋. The comparison naturally skips the middle element for odd-length lists.

Trace Carefully

Edge Cases

Let's verify our solution handles all edge cases:

Edge Case 1: Empty List

Input: None
Output: True (vacuously a palindrome)

Edge Case 2: Single Node

Input: [1]
Output: True

Edge Case 3: Two Nodes, Same Value

Input: [1, 1]
Output: True

Edge Case 4: Two Nodes, Different Values

Input: [1, 2]
Output: False

Edge Case 5: Even Length Palindrome

Input: [1, 2, 2, 1]
Output: True

Edge Case 6: Odd Length Palindrome

Input: [1, 2, 3, 2, 1]
Output: True

Edge Case 7: Odd Length Non-Palindrome

Input: [1, 2, 3, 4, 5]
Output: False

palindrome_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def test_palindrome_edge_cases():
    """Comprehensive edge case testing."""
    
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        curr = head
        for val in values[1:]:
            curr.next = ListNode(val)
            curr = curr.next
        return head
    
    # Test empty list
    assert is_palindrome(None) == True, "Empty list failed"
    
    # Test single node
    assert is_palindrome(create_list([1])) == True, "Single node failed"
    
    # Test two nodes, same
    assert is_palindrome(create_list([1, 1])) == True, "Two same failed"
    
    # Test two nodes, different
    assert is_palindrome(create_list([1, 2])) == False, "Two different failed"
    
    # Test even palindrome
    assert is_palindrome(create_list([1, 2, 2, 1])) == True, "Even palindrome failed"
    
    # Test odd palindrome
    assert is_palindrome(create_list([1, 2, 3, 2, 1])) == True, "Odd palindrome failed"
    
    # Test even non-palindrome
    assert is_palindrome(create_list([1, 2, 3, 4])) == False, "Even non-palindrome failed"
    
    # Test odd non-palindrome
    assert is_palindrome(create_list([1, 2, 3, 4, 5])) == False, "Odd non-palindrome failed"
    
    # Test longer palindrome
    assert is_palindrome(create_list([1,2,3,4,5,4,3,2,1])) == True, "Long palindrome failed"
    
    # Test almost palindrome
    assert is_palindrome(create_list([1,2,3,4,5,5,3,2,1])) == False, "Almost palindrome failed"
    
    print("All palindrome tests passed! ✓")

Common Mistakes and How to Avoid Them

Classic Mistakes in Palindrome Detection

•Wrong slow/fast condition — Using while fast and fast.next vs while fast.next and fast.next.next gives different middle positions. Trace through examples to verify.
•Not handling empty/single-node lists — These are valid palindromes but might cause null pointer errors without explicit checks.
•Comparing wrong halves — After reversing, make sure you're comparing first_half (from head) with second_half (reversed), not mixing them up.
•Forgetting to save second_half_copy — If you restore the list, you need the original start of the reversed half, not the traversed-to-end pointer.
•Not stopping at the right time — Compare while second_half is not null. The first half might be longer (odd-length case), but that's okay.
•Breaking on any false without returning — If you find a mismatch, set a flag but continue to restore if needed, OR return immediately if no restoration required.

The Early Return Trap

Complexity Analysis

Time Complexity: O(n)

Finding middle: O(n/2) — fast traverses whole list
Reversing second half: O(n/2) — half the nodes
Comparing halves: O(n/2) — iterate through half
Optional restoration: O(n/2) — reverse again

Total: O(n/2) + O(n/2) + O(n/2) + O(n/2) = O(2n) = O(n)

Space Complexity: O(1)

A fixed number of pointers: slow, fast, first_half, second_half, prev, curr, next_temp
No data structures that grow with input size
No recursion (unlike the recursive approach)

Why This is Optimal:

We must examine every element to verify palindrome: Ω(n) lower bound
We achieve Θ(n) time with O(1) space—optimal on both fronts

Approach Comparison
Approach	Time	Space	Trade-off
Array copy	O(n)	O(n)	Simple, inefficient space
Recursion	O(n)	O(n) stack	Elegant, stack overflow risk
Reverse half	O(n)	O(1)	Optimal, modifies list temporarily

Synthesis: How Patterns Combine

Palindrome detection is a synthesis problem that draws on multiple patterns we've studied:

Pattern 1: Two-Pointer (Slow/Fast)

Used to find the middle without knowing the length. This appears in:

Finding the middle of a list
Cycle detection (Floyd's algorithm)
Finding kth from end

Pattern 2: List Reversal

Used to enable backwards traversal on a forward-only structure. This appears in:

Reversing a full list
Partial reversal (reverse between positions)
Reordering lists

Pattern 3: Pointer Comparison Walk

Used to compare two lists element by element. This appears in:

Merging sorted lists
Checking list equality
Intersection detection

Problems That Use Similar Synthesis

•Reorder List — Find middle, reverse second half, interleave
•Sort List — Find middle, recursively sort halves, merge
•Rotate List — Find length, find new tail, relink
•Split List in Parts — Calculate part sizes, traverse and sever
•Add Two Numbers II — Reverse, add digit by digit, reverse result

Building Your Toolkit

Summary: Mastering Palindrome Detection

Palindrome detection synthesizes the core linked list patterns into an elegant solution. Let's consolidate the key insights:

Key Takeaways

•The O(1) space solution combines middle-finding (slow/fast) + reversal + comparison—three patterns in one solution.
•Choose the right middle-finding condition — while fast.next and fast.next.next gives the split point we need.
•Reversing the second half enables element-by-element comparison without random access or extra space.
•Restoration is optional but important in production code to avoid modifying the caller's data.
•Edge cases (empty list, single node, two nodes) require explicit handling or careful design.
•This problem is a pattern composition — master the primitives and combinations become natural.

Module Complete:

You've now mastered the five essential linked list patterns that appear repeatedly across problems:

Reversing — Transform traversal direction
Merging — Combine sorted sequences
Nth from End — Use gaps between pointers
Partitioning — Separate by condition
Palindrome Detection — Synthesize all of the above

These patterns form a comprehensive toolkit for linked list problems. With practice, you'll recognize which patterns apply to new problems almost instantly.

Module Complete

5 / 5