Linked Lists
Retrieval: the four habits
Two problems rebuilt cold, plus the checklist that prevents most linked list bugs.
Key idea
Four habits
Save before you overwrite. Any assignment that destroys a reference you still need must be preceded by storing it.
Use a dummy head whenever the front of the list can change. It appeared in five problems here and removed a special case every time.
Return the head from anything that can change it, and use that return value at the call site.
Cut the links you meant to cut. A split that does not set the trailing next to None produces bugs that look like they cannot happen.
Tip
And two pointer arrangements
Different speeds find the middle and detect cycles. A fixed gap measures from the end. Both let you do in one pass what otherwise needs the length, and the length is the thing a linked list will not tell you.
Diagnose the symptom
You split a list into halves, reverse the second half, and interleave them. The program hangs forever. What is the most likely cause?
Reorder List, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Meeting Rooms II, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.