Linked list in place
A node is a value and one pointer. Every problem here is the same job: decide which arrows to move, and in what order, so that nothing is ever lost.
Problems worked on this page, and more to practise
- 206. Reverse Linked List
- 143. Reorder List
- 25. Reverse Nodes in k-Group
- 876. Middle of the Linked List
- 21. Merge Two Sorted Lists
- 141. Linked List Cycle
- 19. Remove Nth Node From End of List
- 24. Swap Nodes in Pairs
- 92. Reverse Linked List II
- 142. Linked List Cycle II
- 234. Palindrome Linked List
- 2. Add Two Numbers
- 138. Copy List with Random Pointer
Why does reversing a linked list need three pointers?
Because the line that turns an arrow round destroys the only way forward. Once cur.next points backwards at prev, nothing in the program reaches the rest of the list unless a third name is already holding it, and that name is nxt. prev is needed too, because a node has no way to reach the one in front of it. Three names, one for the part already done, one for the node being changed, and one for the part not touched yet.
What is a dummy head and when is it worth one?
A dummy head is a throwaway node placed in front of the real head, so that every real node has something in front of it. It is worth one whenever the head itself might change or be deleted, because that is the case that otherwise needs its own branch: merging two lists, deleting the nth node from the end, adding two numbers. You return dummy.next at the end, and the node is thrown away with the rest of the stack frame.
How do the fast and slow pointers find the middle in one pass?
Both start at the head. Slow takes one step per lap and fast takes two, so after i laps slow has covered i nodes and fast has covered 2i. When fast runs out, 2i is about the length, so i is about half of it, and slow is standing on the middle. The same pair detects a cycle: inside a loop the gap between them shrinks by exactly one node per lap, so it reaches zero and they must land on the same node.
Why not copy the values into an array and rebuild the list?
It works and it is the honest first answer to say out loud. It also costs O(n) extra memory and allocates a second node for every node you were given, and most interviewers ask for the in-place version precisely because the pointer discipline is what they are testing. Say the copy version, give its cost, then do it in place.
Should I reverse a linked list recursively or iteratively?
Iteratively, unless you are asked for both. The recursive version is four lines and reads well, but every node puts a frame on the call stack, so it is O(n) space rather than O(1), and CPython stops at about a thousand frames while the problem allows five thousand nodes. Write the loop, then offer the recursion as the follow-up it usually is.