Linked Lists
Reversing in fixed groups
The hardest pointer surgery in the set. Everything you need is already written; the difficulty is bookkeeping.
The task
Reverse the list in consecutive groups of k nodes. If fewer than k nodes remain at the end, leave them alone.
You can already reverse a whole list. Two things are new: reversing only a segment, and reconnecting each reversed segment to the ones on either side.
Why it works
Check the length before touching anything
The rule about leaving a short tail alone means you must know whether k nodes remain before you start reversing. Reversing first and undoing it is possible and horrible.
So each round begins by walking k nodes ahead to confirm they exist. If they do not, the loop stops and the remainder stays as it is. That walk is O(k) per group and O(n) overall, so it costs nothing asymptotically.
Why it works
Name the four things you need
For each group, four references matter and losing any one of them is fatal.
The node before the group, which will need to point at the group's new first node. The group's original first node, which becomes its last and must point at whatever follows. The group's original last node, which becomes its first. And the node after the group, which is where the next round begins.
Write those four down as named variables before writing any assignment. The surgery is short once they exist and impossible to keep straight without them.
Reversing exactly k nodes
Segment reversal is the ordinary reversal loop with a counter instead of a None check, and it returns both ends of what it reversed.
Tip
The tail is left dangling on purpose
After reversing, new_tail.next still points at prev from the loop's perspective, which is why printing new_head stops after three values. The reversed segment is properly terminated.
The caller is responsible for attaching new_tail.next to whatever comes next, which is either the next reversed group or the untouched remainder. Returning all three references is what makes that possible.
Key idea
A dummy head, one last time
The first group's predecessor does not exist, since the group starts at the head. A dummy node before the list supplies one, and the answer is dummy.next as always.
This is the last of the five problems in this unit where the dummy head removes a special case. If you take one habit from this unit, take that one.
How to approach this
Write has_k_more and reverse_k as separate functions and test them on their own. Then the main loop is: while another full group exists, reverse it, stitch it in, and advance the predecessor to the group's new tail.
Attempting it as one function with five pointers is how this problem eats an hour. It is not conceptually hard; it is unforgiving.
Predict the output: attaching the front but not the back
One group of three is reversed and stitched to the front, and then the list is printed. The 4 and the 5 were deliberately left untouched. Type exactly what it prints.
Reverse Nodes In K Group
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.