143. Reorder List
You receive head of a singly linked list L0 → L1 → … → Ln−1. Rearrange the nodes in place so the list interleaves from both ends, folding the back half into the front half:
L0 → Ln−1 → L1 → Ln−2 → L2 → Ln−3 → …
Relink the actual nodes by rewiring their next pointers — treat the values as read-only rather than shuffling them between nodes. The function returns nothing; the judge walks the rewired list from head and prints the values it finds.
A full-credit solution touches each node a constant number of times and uses O(1) extra space: locate the middle, reverse the back half, then zip the two halves together.
Example 1:
Input: head = [1, 2, 3, 4]
Output: list becomes [1, 4, 2, 3]
Explanation: The fold interleaves front and back: L0=1, then L3=4, then L1=2, then L2=3.
Example 2:
Input: head = [1, 2, 3, 4, 5]
Output: list becomes [1, 5, 2, 4, 3]
Explanation: With an odd length the middle node (3) ends up last: 1, 5, 2, 4, 3.
Constraints:
- 1 ≤ number of nodes ≤ 5 * 10⁴
- -1000 ≤ Node.val ≤ 1000
Hints:
If you collect the nodes into an array first, random access does the hard part: walk two indices — one from the front, one from the back — and rewire next pointers as you alternate between them. Just be careful to null-terminate the final node.
For O(1) extra space, chain three standard routines: a slow/fast pointer pair finds the middle, a three-pointer loop reverses the back half, and a zipper merge interleaves the two halves. Each is short; the composition is the whole solution.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4]
Expected output: [1, 4, 2, 3]