Palindrome Linked List

Palindrome Linked List

What is this problem about?

The Palindrome Linked List problem asks whether a singly linked list forms a palindrome when its values are read as a sequence. The challenge is doing this in O(n) time and O(1) space. This easy coding problem requires finding the midpoint, reversing the second half, and comparing. The linked list, recursion, two pointers, and stack interview pattern is the core.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it combines three fundamental linked list operations: finding the middle (slow/fast pointers), reversing a list (in-place), and comparing two lists. The O(1) space constraint forces in-place manipulation.

Algorithmic pattern used

Find middle + reverse second half + compare. Use slow/fast pointers to find the middle. Reverse the second half in-place. Compare first half and reversed second half node by node. Optionally restore the list after comparison. Return true if all values match.

Example explanation

List: 1→2→3→2→1. Slow/fast find middle: slow stops at 3. Reverse 2→1 to 1→2. Compare [1,2,3] with [1,2]: first 2 match. Third element (3) vs null: valid palindrome! Return true.

List: 1→2→3→4→1. Reverse second half: 1→4→3. Compare [1,2] vs [1,4]: mismatch at 2. Return false.

Common mistakes candidates make

• Not handling even vs odd length lists correctly in finding the middle.
• Not restoring the list (good practice to not corrupt the input).
• Using a stack/array (works but O(n) space — interviewers may ask for O(1)).
• Incorrect mid-point detection with slow/fast pointers.

Interview preparation tip

Palindrome Linked List combines three fundamental skills. Practice each independently: (1) find middle of linked list with slow/fast pointers, (2) reverse a linked list in-place, (3) compare two lists element by element. Then combine them. The clean O(1) space solution impresses interviewers because it requires mastery of all three components. Always discuss the optional list restoration step.