Palindrome Linked List

Approach Summary

Find mid with slow/fast pointers, reverse the second half in-place, compare both halves, then restore the list.

Full Solution & Approach

A linked list cannot be indexed from both ends the way an array can, so the standard approach is to split the list in half, reverse the second half in place, and compare the two halves element by element. First find the middle using the slow-and-fast pointer trick: slow advances one node per step while fast advances two, so when fast reaches the end, slow is at the midpoint. Then reverse the second half starting from slow by walking it with three pointers — prev, cur, and next — flipping each cur.next to prev. Now walk the two halves together: if any pair of values differs, the list is not a palindrome; if the reversed half is fully consumed without a mismatch, it is. The comparison only needs to run until the reversed half runs out, which naturally stops at the middle of an odd-length list. Everything happens in place with no extra array, which is the point of the problem — an O(1)-space answer rather than copying the values into an array and using the array palindrome check.

Finding the middle is one pass, reversing the second half is a second pass over half the nodes, and comparing is a third pass — all O(n). Only pointer variables are used, so O(1) extra space (the reverse modifies the list in place).

Solution Code

Solution

def is_palindrome(head: Optional[ListNode]) -> bool:
    # Find the middle with slow/fast pointers
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Reverse the second half (starting at slow)
    prev = None
    while slow:
        nxt = slow.next
        slow.next = prev
        prev = slow
        slow = nxt
    # Compare the two halves
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let prev = null;
  while (slow) {
    const nxt = slow.next;
    slow.next = prev;
    prev = slow;
    slow = nxt;
  }
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }
  return true;
}

public boolean isPalindrome(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode prev = null;
    while (slow != null) {
        ListNode nxt = slow.next;
        slow.next = prev;
        prev = slow;
        slow = nxt;
    }
    ListNode left = head, right = prev;
    while (right != null) {
        if (left.val != right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
}

bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode* prev = nullptr;
    while (slow) {
        ListNode* nxt = slow->next;
        slow->next = prev;
        prev = slow;
        slow = nxt;
    }
    ListNode *left = head, *right = prev;
    while (right) {
        if (left->val != right->val) return false;
        left = left->next;
        right = right->next;
    }
    return true;
}

Edge Cases to Watch

Empty or single-node list — trivially a palindrome
Even-length list — halves split cleanly at the midpoint
Odd-length list — the middle node is excluded from the comparison
All identical values — true even for long lists

How to Recognize This Pattern

"Check palindrome without extra space"
Reverse second half → one-pass comparison

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)