Palindrome Linked List
Given the head of a singly linked list, return true if it reads the same forwards and backwards — using O(1) extra space.
Intuition
You can't walk a singly linked list backwards. So find the middle, reverse the second half in place, then walk the two halves toward each other comparing values. Equal all the way means palindrome.
Approach
Find the middle with slow / fast
Run a slow pointer one step and a fast pointer two steps. When fast reaches the end, slow sits at the midpoint — the start of the second half. This is the same tortoise-and-hare trick used for 'Middle of the Linked List'.
Reverse the second half in place
From slow, reverse the rest of the list using the standard prev/curr pointer flip. Now you have two half-lists: the original front half (still pointing forward) and the reversed back half. No extra array is needed, so space stays O(1).
Walk both halves and compare
Advance one pointer from the head and one from the reversed second half, comparing values node by node. If any pair differs, return false immediately; if you exhaust the shorter half with all matches, it's a palindrome — return true. (The middle node in an odd-length list is ignored, which is correct.)
Solution & live demo
Edge cases
Trivially a palindrome — return true.
For odd length the middle node is unpaired and safely skipped; comparison only spans the matched halves.
If the caller needs the list intact afterward, reverse the second half back; the comparison itself only needs it reversed.