Linked list coding interview questions in Java 3 questions in 2 chapters

Iteratively, I walk the list with two pointers, prev and curr. At each node I save next, point curr back at prev, then move both forward; at the end prev is the new head. That's O(n) time and O(1) extra space. Recursively, I reverse the rest of the list first, then make the next node point back to the current one and clear the current node's next. That's O(n) stack space, so very long lists can overflow.

I use two pointers, slow and fast, both starting at the head. Slow moves one node per step and fast moves two, so when fast reaches the end, slow is in the middle. That's one pass, O(n) time and O(1) space, without counting the length first. For an even-length list this version returns the second of the two middle nodes, so I'd confirm which one the interviewer wants.

I put a dummy node before the head and keep a pointer to the node before the current group. For each group I first check that k nodes remain; if not, I leave the tail as it is. Then I reverse those k nodes with the usual three-pointer loop, starting prev at the node after the group so the reversed group stays connected, and move the group pointer to the old first node. O(n) time, O(1) space.