Full reversal (Linked List — Reversal Sub-pattern)
Walk once, flipping each arrow back to the node before it. The result is the list in reverse order, and the old tail is the new head.
- ›
"reverse the linked list"
- ›
"reverse a doubly linked list" (swap
prevandnexton every node) - ›
"remove nodes that have a bigger node after them" (reverse, filter, reverse back)
- ›
numbers stored most significant first, where the work must start at the units digit
Reverse Linked List is the base move. Reverse a Doubly Linked List has prev pointers too, so swap both arrows on each node. Remove Nodes From Linked List reverses so a running maximum can be read from the right, then reverses back. Add Two Numbers II and Double a Number reverse the digits so the carry starts at the units digit; the difference is that the doubled number may gain a leading digit, which must become a new head.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Reverse Linked ListWalkthroughEasyBasic Anchor·LeetCode #206
- 2Reverse a Doubly Linked ListWalkthroughEasyBasic Reinforcement·GeeksforGeeks
- 3Remove Nodes From Linked ListWalkthroughMediumSlight Variation·LeetCode #2487
- 4Add Two Numbers IIWalkthroughMediumPattern Transfer·LeetCode #445
- 5Double a Number Represented as a Linked ListWalkthroughMediumTricky / Edge Case·LeetCode #2816
Template
// Full reversal: walk once, pointing each node back to the previous one.
// Returns the new head (the old tail).
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // the reversed part so far (empty at first)
ListNode* cur = head; // the next node to flip
while (cur != nullptr) {
ListNode* nxt = cur->next; // 1. save the rest of the list BEFORE losing it
cur->next = prev; // 2. flip this arrow
prev = cur; // 3. the reversed part now starts at cur
cur = nxt; // 4. move on to the saved node
}
return prev; // cur ran off the end, so prev is the old tail
}