Does a linked list read the same both ways? Find the middle with fast and slow runners, reverse the back half, then compare the halves node by node.
▼The problem
LeetCode 234 (Easy). Given the head of a singly linked list, return true if it reads the same forwards and backwards.
Examples (LeetCode's): [1,2,2,1] → true, [1,2] → false; the video adds the odd-length [1,2,3,2,1] → true (the middle node pairs with itself).
The solution
def is_palindrome(head):
slow = fast = head
while fast and fast.next: # find the middle
slow = slow.next
fast = fast.next.next
prev = None # reverse 2nd half
while slow:
nxt = slow.next
slow.next = prev
prev, slow = slow, nxt
left, right = head, prev # compare
while right:
if left.val != right.val:
return False
left, right = left.next, right.next
return TrueTranscript
Palindrome Linked List. Given the head of a singly linked list, does it read the same forwards and backwards? The catch: each node only knows the next one.
One, two, two, one reads the same both ways: true. One, two is false. One, two, three, two, one is true too: with an odd count, the middle stands alone.
The easy way: copy every value into an array, then check it with two pointers from both ends. That's linear time, but the copy costs n extra space.
The key idea: fold the list in half. Slow and fast pointers find the middle. Reverse the second half in place, so it runs back toward the middle. Then walk both halves side by side and compare. Same middle and reverse moves as Reorder List.
In code, fast moves two steps while slow moves one. When fast runs out, slow is at the middle. Flip each next pointer from slow to the end. Then compare left and right until right runs out; any mismatch returns false.
Now one, two, two, one. Slow and fast start at the head. Slow steps to the first two, fast to the second two. Slow steps to the second two, and fast runs off the end. Reverse from there: the last one now points back to two. Compare: one and one match. Two and two match. True.
Each phase is one walk: linear time. Just a few pointers: constant space. To give the list back unchanged, reverse the second half again.
Find the middle, reverse, compare. That's Palindrome Linked List.