How to Solve: Palindrome Linked List

How to Solve: Palindrome Linked List

? Introduction

"This problem appears in 1 out of every 3 Linked List interviews—master it, and you’ll prove you can break down complex constraints into clean, efficient code under pressure."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you’re comfortable with: 1. Linked List Traversal – Iterating, reversing, and splitting lists. 2. Two-Pointer Techniques – Fast/slow pointers for cycle detection and midpoint finding. 3. In-Place Reversal – Modifying a linked list without extra space.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist for Every Palindrome Linked List Problem:

1. Edge Cases First

2. If head is None or head.next is None, return True (empty or single-node lists are palindromes).

3. Find the Middle

4. Use fast & slow pointers to locate the midpoint.

5. fast moves 2 steps, slow moves 1 step → slow ends at the middle.

6. Reverse the Second Half

7. Reverse the sublist starting from slow.next (in-place).

8. Example: 1→2→3→2→1 → Reverse 3→2→1 to 1→2→3.

9. Compare Halves

10. Traverse both halves simultaneously, comparing node values.

11. If all values match → True; else → False.

12. Restore the List (Optional)

13. If the problem requires preserving the original list, reverse the second half again.

14. Time & Space Complexity

15. Time: O(n) (traversal + reversal + comparison).
16. Space: O(1) (in-place reversal, no extra space).

? WORKED EXAMPLES

Example 1 – Basic (LeetCode 234)

Problem: Given a singly linked list, determine if it’s a palindrome.

Solution (Python):

class ListNode:

    def __init__(self, val=0, next=None):

        self.val = val

        self.next = next

def isPalindrome(head: ListNode) -> bool:

    # Step 1: Edge cases

    if not head or not head.next:

        return True


    # Step 2: Find middle (slow)

    slow, fast = head, head

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next


    # Step 3: Reverse second half

    prev = None

    while slow:

        next_node = slow.next

        slow.next = prev

        prev = slow

        slow = next_node


    # Step 4: Compare halves

    left, right = head, prev

    while right:

        if left.val != right.val:

            return False

        left = left.next

        right = right.next


    return True

Why This Works: - Fast & Slow Pointers efficiently find the midpoint. - In-Place Reversal avoids extra space. - Two-Pointer Comparison checks symmetry in O(n) time.

Complexity: - Time: O(n) (3 passes: find middle, reverse, compare). - Space: O(1) (no extra data structures).

Example 2 – Medium (Follow-Up: Preserve Original List)

Problem: Check if a linked list is a palindrome without modifying the original list.

Solution (Python):

def isPalindromePreserve(head: ListNode) -> bool:

    # Step 1: Edge cases

    if not head or not head.next:

        return True


    # Step 2: Find middle (slow)

    slow, fast = head, head

    while fast and fast.next:

        slow = slow.next

        fast = fast.next.next


    # Step 3: Reverse second half (but restore later)

    prev = None

    curr = slow

    while curr:

        next_node = curr.next

        curr.next = prev

        prev = curr

        curr = next_node


    # Step 4: Compare halves

    left, right = head, prev

    is_palindrome = True

    while right:

        if left.val != right.val:

            is_palindrome = False

            break

        left = left.next

        right = right.next


    # Step 5: Restore the list

    curr = prev

    prev = None

    while curr:

        next_node = curr.next

        curr.next = prev

        prev = curr

        curr = next_node


    return is_palindrome

Why This Works: - Reverses and restores the second half to avoid permanent modification. - Same time complexity (O(n)), but extra pass to restore the list.

Complexity: - Time: O(n) (4 passes: find middle, reverse, compare, restore). - Space: O(1) (still in-place).

Example 3 – Hard (Follow-Up: Recursive Approach)

Problem: Solve the problem recursively (less common, but asked in some interviews).

Solution (Python):

def isPalindromeRecursive(head: ListNode) -> bool:

    # Use a helper to track the left node

    self.left = head


    def helper(right):

        if not right:

            return True

        # Recurse to the end

        is_pal = helper(right.next)

        # Compare left and right

        if not is_pal:

            return False

        if self.left.val != right.val:

            return False

        self.left = self.left.next

        return True


    return helper(head)

Why This Works: - Recursion reaches the end of the list, then compares nodes on the way back. - Space: O(n) (call stack), but no extra data structures.

Complexity: - Time: O(n) (traversal + comparison). - Space: O(n) (recursion stack).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Here’s your 60-second recap before the interview:

1. Edge Cases First: Empty or single-node lists? Return True immediately.
2. Find the Middle: Fast pointer moves 2 steps, slow moves 1 → slow is the midpoint.
3. Reverse the Second Half: In-place reversal, no extra space.
4. Compare Halves: Traverse both halves simultaneously.
5. Restore if Needed: If the problem says ‘don’t modify,’ reverse the second half again.
6. Complexity: O(n) time, O(1) space—this is the optimal solution.

If they ask for recursion, know it’s O(n) space. If they ask for preservation, reverse twice. And if they ask for optimization, stick to the two-pointer approach. You’ve got this!

? Final Notes

• Practice Variations: Try solving with a stack (for O(n) space) or recursion (for O(n) space).
• Whiteboard First: Sketch the steps before coding.
• Test Cases: Always test with:
• 1→2→2→1 (palindrome)
• 1→2→3→2→1 (palindrome)
• 1→2→3→4 (not palindrome)
• 1 (single node)
• None (empty list)

Now go crush that interview! ?