Palindrome Linked List | Find Middle & Reverse | Linked List

Overview

Palindrome linked list means checking whether the sequence of values in the list reads the same forward and backward. The constraint is usually O(n) time and O(1) space. The standard approach: (1) find the middle with fast/slow pointers, (2) reverse the second half in-place, (3) compare the first half with the reversed second half, (4) optionally restore the list by reversing the second half again.

Why O(1) space works: You don't need to copy the list into an array; finding the middle and reversing one half can be done with a few pointers.

When to Use

Check if list is palindrome — Classic problem with O(1) space requirement.
Combines Find Middle and Reverse In-Place.

How It Works

Find middle: Use fast/slow; when fast reaches the end, slow is at the middle (or first of two middles). For "second half" we often take the node after slow (or slow itself for "second middle" definition).
Reverse second half: From that node to the end, reverse in-place (prev=null, curr=mid, rewire next pointers).
Compare: One pointer at head, one at the head of the reversed second half; step both and compare values until the second-half pointer reaches null.
Optional: Reverse the second half again to restore the original list.

Example 1: Palindrome Check (O(1) Space)

Problem: Given the head of a singly linked list, return true if it is a palindrome. O(n) time, O(1) space.

function isPalindrome(head: ListNode | null): boolean {
  if (head === null || head.next === null) return true;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast?.next !== null) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  let second: ListNode | null = reverseList(slow);
  let first: ListNode | null = head;
  while (second !== null) {
    if (first!.val !== second.val) return false;
    first = first!.next;
    second = second.next;
  }
  return true;
}
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr: ListNode | null = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

Time: O(n), Space: O(1). The list is modified (second half reversed); restore by reversing again if needed.

Example 2: With Restore (Optional)

After comparison, reverse the second half again starting from the node you reversed (you need to keep a reference to the start of the second half before reversing, or recompute the middle).

Edge Cases

Empty list — Treat as palindrome (or per problem: return true).
Single node — Return true.
Two nodes — Compare both values; slow may be at first or second node depending on "first middle" vs "second middle"; adjust so you compare the two halves correctly (e.g. second half = slow.next for even length).
Odd length — The exact middle node is skipped in comparison (it's the same from both sides).

Common Mistakes

Comparing too far — Stop comparison when the second-half pointer reaches null; don't compare the first half past that (first half might have one extra node in odd-length case).
Wrong middle — For even length, second half should start after the first middle so both halves have the same length; for odd, the middle node is shared and can be skipped in the compare loop.
Modifying the list — If the problem says "don't modify," you need O(n) extra space (e.g. copy to array and two pointers from both ends).

Time and Space Complexity

Time: O(n) — find middle O(n), reverse O(n), compare O(n).
Space: O(1) if you allow in-place reverse; O(n) if you must not modify (e.g. array).

Summary

Palindrome: Find middle → reverse second half → compare first half with reversed second half; optionally restore.
Uses Fast and Slow Pointers and Reverse In-Place. See Find Middle for middle variants.