Given the head of a singly linked list, decide whether it reads the same both ways. Aim for O of n time and O of 1 space.
DSA Animator › DSA Revision › Linked List › Palindrome Linked List
Remember: middle, reverse, compare. Three small linked list tools combine into one solution. The video solves Palindrome Linked List (LeetCode 234, Easy) with the Fast & Slow + Reverse pattern from the Linked List topic, and you can replay every step in the interactive Palindrome Linked List animation.
Given the head of a singly linked list, decide whether it reads the same both ways. Aim for O of n time and O of 1 space.
For 1, 2, 2, 1, the answer is true.
Copying the values into an array and checking with two pointers uses O of n space. We cannot walk a singly linked list backwards.
Find the middle with fast and slow pointers. Reverse the second half. Then compare the first half with the reversed second half, node by node.
Slow stops at the second 2, which starts the second half. Reverse it, so the second half reads 1, 2. Compare 1 with 1, and 2 with 2. Everything matched, so it is a palindrome.
In code, move fast twice and slow once to find the middle. Reverse from slow, using the same three-pointer loop. Walk both halves and return false on any mismatch, so it's O of n time and O of 1 space.
Remember: middle, reverse, compare. Three small linked list tools combine into one solution.