{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Palindrome Linked List – Solution & Complexity

Interview solutions
/
Palindrome Linked List

Solution Walkthrough

  1. Step 1: Understand the Goal

    • A linked list is a palindrome when its node values read the same forwards and backwards.
    • The interview challenge is doing this in O(1) extra space — you cannot index into a linked list, and copying all values to an array uses O(n) space.
    • The trick is to reverse only the second half in place and compare it against the first half.

  2. Step 2: Find the Middle with Fast/Slow Pointers

    • Advance a slow pointer one node at a time and a fast pointer two nodes at a time.
    • When fast reaches the end, slow sits at the middle of the list.
    • With the array framing, the same idea is a midpoint index len(head) // 2.
    mid = len(head) // 2
first_half = head[:mid]
second_half = head[mid:]

  3. Step 3: Reverse the Second Half and Compare

    • Reverse the second half of the list (in the real linked-list version this is an in-place pointer reversal).
    • Walk both halves in step and compare values; if any pair differs, it is not a palindrome.
    • An odd-length middle element can be ignored because it mirrors itself.
    second_half = second_half[::-1]
for a, b in zip(first_half, second_half):
    if a != b:
        return False
return True

  4. Step 4: Final Complete Solution

    • Finding the middle, reversing the second half, and comparing each take a single pass, so the total time is O(n).
    • The in-place reversal keeps extra space at O(1) for a true linked list. With the array framing, a symmetric two-pointer scan is the simplest correct approach.
    def is_palindrome(head: list[int]) -> bool:
    left, right = 0, len(head) - 1
    while left < right:
        if head[left] != head[right]:
            return False
        left += 1
        right -= 1
    return True

FAQ

See also

Practice Palindrome Linked List online (run code in the browser)Linked List Cycle solution (easy)Linked List Cycle II solution (medium)Merge Two Sorted Lists solution (easy)Odd Even Linked List solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?