Palindrome Linked List — LeetCode 234 Walkthrough

Palindrome Linked List (#234) is one of those LeetCode problems that looks trivial at first glance — just check if a list reads the same forwards and backwards. But the optimal solution requires combining two fundamental linked list techniques: fast/slow pointers to find the middle and in-place reversal to compare halves without extra space.

This problem appears frequently in coding interviews because it tests whether you truly understand linked list manipulation, not just whether you can copy values into an array. The O(1) space solution is elegant and reveals how multiple patterns compose together in real interview questions.

In this walkthrough, we will cover both approaches — the straightforward array copy and the optimal reverse-second-half technique — so you understand the tradeoffs and can explain your reasoning to an interviewer.

Given the head of a singly linked list, determine if it is a palindrome. A palindrome reads the same forward and backward — so a list like 1 -> 2 -> 2 -> 1 is a palindrome, while 1 -> 2 -> 3 is not.

The challenge is that singly linked lists only allow forward traversal. You cannot simply walk backwards from the tail comparing nodes. This constraint is what makes the problem interesting and why it tests more than basic list traversal.

LeetCode asks for O(n) time and O(1) space as the follow-up, which rules out copying values into an auxiliary data structure. Achieving both constraints simultaneously is what separates a good solution from a great one.

The most intuitive approach to check palindrome linked list is to copy all node values into an array, then use two pointers (one at each end) to verify the palindrome property. This works because arrays support random access and backward traversal, which linked lists do not.

Walk through the list once to collect values into an array. Then set a left pointer at index 0 and a right pointer at the last index. Compare values at both pointers, moving them toward the center. If any pair mismatches, return false. If all pairs match, the list is a palindrome.

This approach runs in O(n) time and O(n) space. It is perfectly acceptable as a first solution in an interview, and many candidates start here before optimizing. The interviewer will likely ask if you can do better on space.

The optimal leetcode 234 solution avoids extra space entirely by modifying the list in place. The key insight is that you only need to compare the first half against the second half — and if you reverse the second half, you can compare both halves by walking forward through each.

This approach uses the fast slow pointer palindrome technique. Start both pointers at the head. Move the fast pointer two steps and the slow pointer one step on each iteration. When the fast pointer reaches the end, the slow pointer is at the middle of the list.

From the middle, reverse the second half of the linked list in place. Now you have two separate halves: the original first half and the reversed second half. Walk through both simultaneously, comparing node values. If every pair matches, the list is a palindrome.

Finding the middle correctly is crucial. When the list has an even number of nodes (1 -> 2 -> 2 -> 1), slow ends up at the start of the second half. When odd (1 -> 2 -> 3 -> 2 -> 1), slow lands on the center node, and you reverse starting from slow.next. Handle both cases by checking whether fast and fast.next are null.

The reverse half linked list step uses the standard iterative reversal technique. Maintain three pointers: prev (starts null), curr (starts at middle), and next (temp storage). On each step, save curr.next, point curr.next to prev, advance prev to curr, and advance curr to the saved next. After the loop, prev points to the new head of the reversed half.

For the comparison phase, walk two pointers — one from the original head and one from the reversed second half head. Compare values at each step. The first half pointer should stop when the second half pointer reaches null. This naturally handles both even and odd length lists.

If the interviewer asks about restoring the list, simply reverse the second half again after comparison and reconnect it to the first half. This shows you understand that modifying input data can have side effects in production code — a detail that demonstrates engineering maturity.

A single-node list is always a palindrome — there is nothing to compare against, so return true immediately. An empty list (null head) is also considered a palindrome by convention, and your code should handle this gracefully without a null pointer exception.

Two nodes with the same value (1 -> 1) is a palindrome. Two nodes with different values (1 -> 2) is not. These are the smallest non-trivial cases and are worth tracing through your code mentally before submitting.

Odd-length lists require careful handling at the middle node. In the reverse-half approach, the center element does not need to be compared — it is equal to itself. Make sure your slow pointer advances past it before reversing, or your comparison loop will encounter a mismatch.

This problem is a masterclass in pattern composition. The fast slow pointer palindrome technique for finding the middle appears in dozens of linked list problems — from detecting cycles (#141) to finding the start of a cycle (#142) to reorder list (#143). Mastering it here gives you a reusable building block.

The in-place reversal pattern is equally fundamental. Reverse Linked List (#206) is its own problem, but here you apply it to just half the list, which is a more nuanced application. This kind of partial reversal shows up in problems like Reverse Nodes in k-Group (#25) and Swap Nodes in Pairs (#24).

Together, these two patterns form the foundation for some of the most commonly asked linked list questions. If you can find the middle and reverse a segment confidently, you are equipped to handle the majority of linked list problems in real interviews. Drill both patterns with YeetCode flashcards until they feel automatic.