Palindrome Linked List

Problem

Given the head of a singly linked list, return True if it is a palindrome, False otherwise. Solve in O(n) time and O(1) space.

Input: 1->2->2->1  → True
Input: 1->2->1     → True
Input: 1->2        → False

Solution

Approach: Fast/slow midpoint, reverse the second half, then compare.

A palindrome reads the same in both directions, but a singly linked list only walks forward - so the move is to make the back half also walk forward by reversing it, then compare the two halves head to head. Step one finds the midpoint with the runner technique: slow advances one and fast two under while fast and fast.next. When fast runs out, slow is at the end of the first half (even length) or on the exact middle node (odd length). Step two reverses the list starting at slow using the standard three-pointer reversal, returning second as the head of the now-backward tail. Step three walks first = head and second in lockstep, returning False on the first value mismatch.

The comparison loops on while second, which terminates cleanly for both parities: it walks only as far as the reversed tail reaches, and on odd lengths the middle node is compared against itself, costing nothing. Trace [1,2,3,2,1]: slow lands on 3; reversing from 3 gives 1->2->3; comparing 1==1, 2==2, 3==3, then second becomes None and the walk returns true.

Edge cases: A single node leaves second pointing at the middle node whose reversed remainder is just itself; the values match and it returns True. Two distinct values like [1,2] mismatch immediately and return False.

Complexity: O(n) time, O(1) space - three linear passes, all in-place pointer work.