Linked List Palindrome

Tags

Linked List Palindrome

Category

Linked Lists

Difficulty

Hard

Problem Statement

Given the head of a singly linked list, determine whether the linked list is a palindrome. A linked list is a palindrome if the sequence of values reads the same forwards and backwards. The algorithm should ideally use O(1) extra space.

Intuition

To check if a linked list is a palindrome in O(1) space, we can reverse the second half of the list and then compare it with the first half. We find the midpoint using the slow/fast pointer technique, reverse the second half in place, compare the two halves node by node, and optionally restore the list to its original state.

Approach

  1. Use a slow pointer (moves 1 step) and a fast pointer (moves 2 steps) to find the middle of the list.
  2. When the fast pointer reaches the end, the slow pointer is at the midpoint.
  3. Reverse the second half of the linked list starting from the slow pointer.
  4. Compare the first half (from head) and the reversed second half node by node.
  5. If all corresponding values match, the list is a palindrome.
  6. Optionally, reverse the second half again to restore the original list structure.

Pseudocode

function linkedListPalindrome(head):
    if head is null or head.next is null:
        return true

    // Find middle
    slow = head
    fast = head

    while fast is not null and fast.next is not null:
        slow = slow.next
        fast = fast.next.next

    // Reverse second half
    secondHalfHead = reverseList(slow)

    // Compare halves
    firstHalf = head
    secondHalf = secondHalfHead

    while secondHalf is not null:
        if firstHalf.value != secondHalf.value:
            // Optionally restore: reverseList(secondHalfHead)
            return false
        firstHalf = firstHalf.next
        secondHalf = secondHalf.next

    // Optionally restore: reverseList(secondHalfHead)
    return true

function reverseList(head):
    prev = null
    current = head
    while current is not null:
        nextNode = current.next
        current.next = prev
        prev = current
        current = nextNode
    return prev

Time & Space Complexity

  • Time: O(n) where n is the number of nodes. Finding the middle takes O(n/2), reversing takes O(n/2), and comparison takes O(n/2).
  • Space: O(1) extra space. The list is modified in place; no additional data structures are used.

Key Insights

  • The slow/fast pointer technique reliably finds the midpoint in a single pass.
  • For odd-length lists, the middle node is shared and does not affect the palindrome comparison since it matches with itself.
  • Reversing only the second half avoids the need for a stack or array, achieving O(1) space.
  • Restoring the list after checking is good practice, especially if the list is used elsewhere.
  • An alternative O(n) space approach uses a stack: push all values, then traverse again comparing with popped values.

Edge Cases

  • Empty list — considered a palindrome (vacuously true).
  • Single node — always a palindrome.
  • Two nodes — palindrome only if both values are equal.
  • Even-length palindrome (e.g., 1->2->2->1) — the split is clean at the midpoint.
  • Odd-length palindrome (e.g., 1->2->1) — the middle element is its own mirror.
  • All nodes have the same value — always a palindrome regardless of length.
  • Very long list — the O(1) space approach is crucial for memory efficiency.

Linked mentions