Card 08/ 08
Recap: Linked List Reversal
Save next, point back, move prev, move curr; add a dummy for a stretch, and a count for groups.
Linked list reversal turns each next reference round in one pass with prev, curr and next, in four lines whose order never changes: save next, set curr.next to prev, move prev, move curr. The nodes behind curr are always a reversed list headed by prev, and the function returns prev. Every variation keeps those lines and adds what the task needs:
| Task | References | Extra node | Cost |
|---|---|---|---|
| Reverse the whole list | prev, curr, next | None | O(n) time, O(1) space |
| Reverse positions a to b | before, prev, curr, next | A dummy before the head | O(b) time, O(1) space |
| Check a palindrome | slow, fast, then two walkers | None | O(n) time, O(1) space |
| Reverse in groups of k | before, end, prev, curr, next | A dummy before the head | O(n) time, O(1) space |
Saving next before curr.next changes must come first: flip first and the rest of the list is lost with no error. A dummy node gives the head a node before it, so a stretch or group starting at position 1 needs no special case.
← → move through sections and cards