{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Palindrome Linked List – Solution & Complexity

Interview solutions
/
Palindrome Linked List

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. 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. 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. 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)Container With Most Water solution (medium)Find the Index of the First Occurrence in a String solution (easy)Is Subsequence solution (easy)Move Zeroes solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?