Subtitle / Summary
The core of palindrome validation is symmetric comparison, but a singly linked list cannot move backward. The most stable engineering template is: find middle -> reverse second half in-place -> compare -> reverse back to restore.

  • Reading time: 10-14 min
  • Tags: Hot100, linked list, fast slow pointers, in-place reverse
  • SEO keywords: Palindrome Linked List, fast slow pointers, reverse second half, O(1) space, LeetCode 234
  • Meta description: O(n)/O(1) palindrome check for singly linked list with middle detection, second-half reversal, comparison, and full structure restoration.

A - Algorithm (Problem and Algorithm)

Problem Restatement

Given the head of a singly linked list head, return true if it is a palindrome; otherwise return false.

Input / Output

NameTypeDescription
headListNodehead of singly linked list
returnboolwhether list is palindrome

Example 1

input:  1 -> 2 -> 2 -> 1
output: true

Example 2

input:  1 -> 2
output: false

Target Readers

  • Hot100 learners who want to master the “middle + reverse” linked-list combo
  • Developers who frequently solve palindrome/symmetry interview questions
  • Engineers who care about low extra memory and non-destructive checks

Background / Motivation

For arrays, palindrome check is easy with two pointers from both ends. For singly linked lists, you can only move forward via next, so symmetric comparison is not direct.

Real engineering constraints are often similar to this problem:

  • avoid O(n) extra containers if possible
  • do not permanently mutate the structure
  • keep linear time

So we need a template that is:

  • O(n) time
  • O(1) extra space
  • restorable (no side effects after checking)

Core Concepts

ConceptMeaningPurpose
Palindromesame sequence forward and backwardneeds symmetric comparison
Fast/slow pointersfast moves 2, slow moves 1find middle in O(n)
In-place reversereverse pointer direction on second halfmake backward side comparable forward
Restore stepreverse second half again and reconnectpreserve original structure

C - Concepts (Core Ideas)

How To Build The Solution From Scratch

Step 1: Start from the real obstacle, not the word “palindrome”

Take:

1 -> 2 -> 3 -> 2 -> 1

To verify a palindrome, we want to compare:

  • first node with last node
  • second node with second-last node

But a singly linked list cannot move backward. That is the whole difficulty.

Step 2: Acknowledge the direct solution first

The simplest correct approach is:

  1. copy values into an array
  2. compare from both ends

This is easy, but it uses O(n) extra space. So the real challenge is:

can we make the list itself expose a forward-comparable second half?

Step 3: Ask what transformation would make symmetric comparison possible

If the second half were reversed in place, then both sides could be read forward.

For:

1 -> 2 -> 3 -> 2 -> 1

after reversing the second half, the comparable fronts become:

left forward:   1 -> 2 -> 3
right forward:  1 -> 2

Now the palindrome check becomes an ordinary two-pointer forward scan.

Step 4: Decide where the second half begins

We first need the end of the first half. Fast/slow pointers do exactly that:

fast = head
slow = head
while fast.next and fast.next.next:
    fast = fast.next.next
    slow = slow.next

When the loop ends:

  • slow is the middle for odd length
  • slow is the left-middle tail for even length

So slow.next is the start of the second half we want to reverse.

Step 5: Reverse only the second half

Now run the standard list reversal on:

second_half_start = reverse_list(first_half_end.next)

This does not solve the whole problem yet. It only converts the hidden backward comparison into a visible forward comparison.

Step 6: Compare, then restore

Use two pointers:

  • p1 from the original head
  • p2 from the reversed second half

If every compared pair matches, the list is a palindrome. Then reverse the second half again and reconnect it, so the original structure is preserved.

That restoration step matters in real code, not just in interviews.

Step 7: Walk one trace slowly

For:

1 -> 2 -> 2 -> 1

the first half ends at the first 2. Reverse the second half:

1 -> 2 -> 1 -> 2
        ^
    reversed start

Now compare:

  • 1 vs 1
  • 2 vs 2

All pairs match, so return True, then restore the suffix.

Step 8: Reduce the method to one sentence

LeetCode 234 is “find the midpoint, reverse the second half to make comparison forward-only, compare both halves, then restore.”

Assemble the Full Code

from __future__ import annotations


class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next: ListNode | None = None


def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def end_of_first_half(head: ListNode) -> ListNode:
    fast = head
    slow = head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next  # type: ignore[assignment]
    return slow


def is_palindrome(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True

    first_half_end = end_of_first_half(head)
    second_half_start = reverse_list(first_half_end.next)

    p1 = head
    p2 = second_half_start
    ok = True
    while ok and p2 is not None:
        if p1.val != p2.val:
            ok = False
        p1 = p1.next  # type: ignore[assignment]
        p2 = p2.next

    first_half_end.next = reverse_list(second_half_start)  # restore
    return ok

Reference Answer

from __future__ import annotations


class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next: ListNode | None = None


def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def end_of_first_half(head: ListNode) -> ListNode:
    fast, slow = head, head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next  # type: ignore[assignment]
    return slow


def is_palindrome(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True
    first_half_end = end_of_first_half(head)
    second_half_start = reverse_list(first_half_end.next)
    p1, p2 = head, second_half_start
    ok = True
    while ok and p2:
        if p1.val != p2.val:
            ok = False
        p1 = p1.next  # type: ignore[assignment]
        p2 = p2.next
    first_half_end.next = reverse_list(second_half_start)
    return ok

Method Category

  • Fast/slow pointer middle finding
  • In-place linked-list reversal
  • Temporary mutation + restoration

Stable handling for odd/even lengths

A robust implementation uses end_of_first_half:

  • odd length: first-half end is exact middle (middle value can be skipped in comparison)
  • even length: first-half end is left-middle

Then reverse first_half_end.next, and compare only while second-half pointer is not null. This removes many odd/even branch bugs.

Key invariant

After reversing second half:

  • p1 starts from head
  • p2 starts from reversed_second_half_head

For palindrome lists, p1.val == p2.val for all nodes in second half.

After check:

  • reverse second half again
  • reconnect via first_half_end.next

So external observers see the original structure.

Practical Guide / Steps

  1. Return true for empty list or single node
  2. Find first_half_end by fast/slow pointers
  3. Reverse first_half_end.next to get second_half_start
  4. Compare head and second_half_start node values
  5. Restore: first_half_end.next = reverse(second_half_start)
  6. Return comparison result

Runnable Python example (palindrome_list.py):

from __future__ import annotations


class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next: ListNode | None = None


def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def end_of_first_half(head: ListNode) -> ListNode:
    fast = head
    slow = head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next  # type: ignore[assignment]
    return slow


def is_palindrome(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True

    first_half_end = end_of_first_half(head)
    second_half_start = reverse_list(first_half_end.next)

    p1 = head
    p2 = second_half_start
    ok = True
    while ok and p2 is not None:
        if p1.val != p2.val:
            ok = False
        p1 = p1.next  # type: ignore[assignment]
        p2 = p2.next

    first_half_end.next = reverse_list(second_half_start)  # restore
    return ok

Explanation / Why This Works

A singly linked list cannot directly read from tail to head. Reversing the second half transforms the “backward side” into a forward list. So palindrome checking becomes simple forward pair comparison.

The important engineering detail is restoration:

  • temporary mutation is acceptable
  • permanent mutation is usually not

By reversing the second half again, we restore exact original topology.

E - Engineering (Real-world Scenarios)

Scenario 1: symmetric event-chain validation (Python)

Background: a rule engine stores a session as a linked event chain and needs to detect mirrored behavior patterns.
Why it fits: O(1) extra memory check without allocating a full copy.

def is_symmetric_chain(head):
    return is_palindrome(head)

Scenario 2: embedded frame-sequence symmetry check (C)

Background: in memory-limited systems, sampled frames may be chained via next pointers.
Why it fits: avoids O(n) buffer allocation and preserves structure after check.

struct ListNode { int val; struct ListNode* next; };

static struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* prev = 0;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

Scenario 3: browser operation-history mirror detection (JavaScript)

Background: editor actions are represented as a linked list in a demo tool.
Why it fits: pointer-based structure allows direct reuse of middle+reverse template.

function reverse(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

R - Reflection

Complexity

  • Time: O(n) (middle find + reverse + compare + restore are all linear)
  • Space: O(1)

Alternatives and Tradeoffs

MethodTimeExtra SpaceTradeoff
Copy to arrayO(n)O(n)easy but memory-heavy
Stack half valuesO(n)O(n)less copy than full array, still linear extra space
Recursion compareO(n)O(n)stack risk on long lists
Reverse second half (current)O(n)O(1)most practical, but needs careful restore

Common Mistakes

  1. Forget restore step, leaving list mutated
  2. Middle handling bug for odd/even length
  3. Wrong compare range (comparing beyond second half)
  4. Missing cycle assumption in non-LeetCode environments

Why this method is practical optimum

It achieves linear time with constant extra memory, and can preserve original list by restoration. This is usually the best tradeoff under production-style constraints.

FAQ and Notes

  1. Why compare only while p2 is not null?
    Second half length is less than or equal to first half length; this covers all mirrored pairs.

  2. What if list has a cycle?
    LeetCode input has no cycle. In production, detect cycle first (Floyd) before this template.

  3. Will reversal damage original structure?
    Temporarily yes; final reverse+reconnect restores it.

  4. Can I skip restore in interview?
    Depends on interviewer constraints. In engineering code, restoration is strongly recommended.

Best Practices

  • Use one stable template: first_half_end + reverse(first_half_end.next)
  • Keep restore step mandatory unless explicitly allowed to mutate
  • Test both odd and even lengths, plus edge cases ([], [x], non-palindrome near center)

S - Summary

  • Singly linked lists cannot directly do backward traversal for symmetry checks.
  • Fast/slow pointers locate split point in O(n).
  • Reversing second half converts backward comparison into forward comparison.
  • Restore step preserves original structure and avoids side effects.
  • This template transfers to many list problems using “middle + half processing”.
  • LeetCode 234. Palindrome Linked List
  • LeetCode 206. Reverse Linked List
  • LeetCode 143. Reorder List
  • LeetCode 876. Middle of the Linked List

Conclusion

The value of this problem is not only palindrome checking. It is a reusable engineering pattern: locate middle, temporarily transform half, compare, restore.

References

Meta Info

  • Reading time: 10-14 min
  • Tags: Hot100, linked list, palindrome, fast slow pointers, in-place reverse
  • SEO keywords: Palindrome Linked List, reverse second half, O(1) space, LeetCode 234, Hot100
  • Meta description: O(n)/O(1) palindrome check by fast/slow split, reverse second half, compare, and restore.

Call To Action (CTA)

After this one, solve these in order with the same skill set:

  1. 206 Reverse Linked List
  2. 143 Reorder List
  3. 92 Reverse Linked List II

Treat them as one template family, not isolated questions.

Multi-language Implementations (Python / C / C++ / Go / Rust / JS)

from __future__ import annotations


class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next: ListNode | None = None


def reverse_list(head: ListNode | None) -> ListNode | None:
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def end_of_first_half(head: ListNode) -> ListNode:
    fast, slow = head, head
    while fast.next and fast.next.next:
        fast = fast.next.next
        slow = slow.next  # type: ignore[assignment]
    return slow


def is_palindrome(head: ListNode | None) -> bool:
    if head is None or head.next is None:
        return True
    first_half_end = end_of_first_half(head)
    second_half_start = reverse_list(first_half_end.next)
    p1, p2 = head, second_half_start
    ok = True
    while ok and p2:
        if p1.val != p2.val:
            ok = False
        p1 = p1.next  # type: ignore[assignment]
        p2 = p2.next
    first_half_end.next = reverse_list(second_half_start)
    return ok

struct ListNode {
    int val;
    struct ListNode *next;
};

static struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* prev = 0;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

static struct ListNode* endFirstHalf(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

int isPalindrome(struct ListNode* head) {
    if (!head || !head->next) return 1;
    struct ListNode* firstEnd = endFirstHalf(head);
    struct ListNode* second = reverse(firstEnd->next);
    int ok = 1;
    struct ListNode *p1 = head, *p2 = second;
    while (ok && p2) {
        if (p1->val != p2->val) ok = 0;
        p1 = p1->next;
        p2 = p2->next;
    }
    firstEnd->next = reverse(second);
    return ok;
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

static ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

static ListNode* endFirstHalf(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
    ListNode* firstEnd = endFirstHalf(head);
    ListNode* second = reverse(firstEnd->next);
    bool ok = true;
    ListNode *p1 = head, *p2 = second;
    while (ok && p2) {
        if (p1->val != p2->val) ok = false;
        p1 = p1->next;
        p2 = p2->next;
    }
    firstEnd->next = reverse(second);
    return ok;
}

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverse(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		nxt := cur.Next
		cur.Next = prev
		prev = cur
		cur = nxt
	}
	return prev
}

func endFirstHalf(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	return slow
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	firstEnd := endFirstHalf(head)
	second := reverse(firstEnd.Next)
	ok := true
	p1, p2 := head, second
	for ok && p2 != nil {
		if p1.Val != p2.Val {
			ok = false
		}
		p1 = p1.Next
		p2 = p2.Next
	}
	firstEnd.Next = reverse(second)
	return ok
}

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
    let mut vals: Vec<i32> = Vec::new();
    let mut cur = head.as_ref();
    while let Some(node) = cur {
        vals.push(node.val);
        cur = node.next.as_ref();
    }
    let mut i = 0usize;
    let mut j = vals.len().saturating_sub(1);
    while i < j {
        if vals[i] != vals[j] {
            return false;
        }
        i += 1;
        j = j.saturating_sub(1);
    }
    true
}

function reverse(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  return prev;
}

function endFirstHalf(head) {
  let fast = head, slow = head;
  while (fast.next && fast.next.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}

function isPalindrome(head) {
  if (!head || !head.next) return true;
  const firstEnd = endFirstHalf(head);
  const second = reverse(firstEnd.next);
  let ok = true;
  let p1 = head, p2 = second;
  while (ok && p2) {
    if (p1.val !== p2.val) ok = false;
    p1 = p1.next;
    p2 = p2.next;
  }
  firstEnd.next = reverse(second);
  return ok;
}