537. Middle of the Linked List
You are given the head of a singly linked list. Return the middle node of the list.
For a list of n nodes the middle is the node at 0-based index n // 2 — so when n is odd it is the exact center, and when n is even (two candidates) you must return the second of the two middle nodes. The list is returned from that node onward, so your answer is judged by the values from the middle node through the tail.
Example 1:
Input: head = [1, 2, 3, 4, 5]
Output: the node holding 3 → [3, 4, 5]
Explanation: Five nodes, so the middle is index 5 // 2 = 2 — the node holding 3. The list from that node onward reads 3, 4, 5.
Example 2:
Input: head = [1, 2, 3, 4, 5, 6]
Output: the node holding 4 → [4, 5, 6]
Explanation: Six nodes leave two candidates, the nodes holding 3 and 4. The rule picks the second one — index 6 // 2 = 3, the node holding 4.
Constraints:
- 1 ≤ number of nodes ≤ 100
- 1 ≤ Node.val ≤ 100
Hints:
A linked list hides its length: you can't jump to index n // 2, you can only follow next pointers. The obvious fix is two passes — count the nodes, then walk n // 2 steps from the head.
One pass is enough with two pointers moving at different speeds: advance slow by one node and fast by two. When fast falls off the end, slow is standing exactly on the middle — and the loop condition `while fast and fast.next` lands on the *second* middle for even lengths automatically.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [1, 2, 3, 4, 5]
Expected output: [3, 4, 5]