A linked list node knows exactly one thing about the world: what comes after it. Not what came before, not how far it is from the end, not whether the walk you started will ever terminate. Every technique in this post exists to recover one of those facts.
That is the whole pattern. Array problems start with random access, a length, and a stable index for every element. Linked list problems start with none of that, and the interviewer is testing whether you can rebuild the specific piece you need in one pass and constant space. Once you see a problem as “which missing fact does this need”, the solutions stop being thirteen separate tricks and become six.
The problems below come from a session deck by Joseph Choi. I compiled and tested every solution here with -fsanitize=undefined,address before writing about it, including the deck’s own code. Most of it holds up. Two pieces do not, and I say so and show why in the closing section rather than quietly rewriting them.
| # | Problem | Difficulty | Missing fact it recovers |
|---|---|---|---|
| 21 | Merge Two Sorted Lists | Easy | a position before the first node |
| 206 | Reverse Linked List | Easy | the previous node |
| 141 | Linked List Cycle | Easy | whether the walk terminates |
| 142 | Linked List Cycle II | Medium | where the walk starts repeating |
| 146 | LRU Cache | Medium | O(1) access into the middle |
| 2 | Add Two Numbers | Medium | a position before the first node |
| 19 | Remove Nth Node From End | Medium | distance from the end |
| 138 | Copy List with Random Pointer | Medium | which copy corresponds to which original |
| 92 | Reverse Linked List II | Medium | the previous node |
| 61 | Rotate List | Medium | the length |
| 707 | Design Linked List | Medium | all of the above, by contract |
| 23 | Merge k Sorted Lists | Hard | the smallest head across k lists |
| 426 | Convert BST to Sorted DLL (Premium) | Medium | nothing — see the misfits section |
| 708 | Insert into a Sorted Circular List (Premium) | Medium | nothing — see the misfits section |
Two of these, 426 and 708, are LeetCode Premium problems. You can read the statements without a subscription but cannot submit against the judge. LC 142 is not in the deck, but the deck derives its algebra under the LC 141 heading, so it belongs here. LC 19 is listed in the deck’s table of contents but its slides did not make it into the file, so the solution below is mine.
What a node cannot tell you
Before any technique, it is worth being precise about the deficit. Here is what an array hands you for free, what a bare ListNode* gives you instead, and which technique closes the gap. The rest of this post is that last column.
| An array gives you | A ListNode* gives you | How you rebuild it |
|---|---|---|
a[i] in O(1) | only p and p->next | walk it, or keep a hash map from key to node (146) |
a.size() | nothing | a counting pass, or close the list into a ring (61) |
a[i-1] | nothing | carry a prev pointer alongside curr (206, 92) |
| a valid slot before element 0 | head is already element 0 | a sentinel node in front (21, 2, 19, 92, 23, 707) |
a[a.size()-k] | nothing | two pointers a fixed gap apart (19) |
| guaranteed termination | next may point backwards | two pointers at different speeds (141, 142) |
| a stable index per element | pointer identity only | weave the copies into the original (138) |
Notice that four of the seven rows are solved by a second pointer. That is not a coincidence. A single pointer is a position; two pointers are a relationship, and a relationship is enough to encode a distance, a speed ratio, or a boundary.
The head is a special case, and you can delete the special case
Look at what these four problems have in common. In LC 21 you do not know which list contributes the first node until you compare. In LC 2 the result list does not exist yet, so there is no head to attach to. In LC 19 the node you remove might be the head. In LC 707 a caller can insert at index 0 at any time.
In each case the branch is the same shape: “if this is the first node, assign to head; otherwise assign to prev->next.” That branch is where most linked list bugs live, and it is entirely avoidable. Allocate one node that is not part of the answer, point it at the real head, and now every node in the list has a predecessor. There is no first node any more.
ListNode dummy(0, head); // dummy.next is head; dummy itself is never returned
// ... rewire freely, treating dummy as "the node before the beginning" ...
return dummy.next; // whatever ended up first is the answerPut it on the stack. The deck writes new ListNode(-1) for this in LC 21, LC 2 and LC 23, which works but leaks one node per call. LeakSanitizer counts them: 4,000 calls to the deck’s mergeTwoLists leaked exactly 4,000 nodes. On the judge nobody notices. In a code review someone will.
LC 21 — Merge Two Sorted Lists
This is the merge step of merge sort with pointers instead of indices. Walk both lists, append the smaller head, advance that list. The sentinel absorbs the “which list starts the answer” question, and the final line absorbs the “one list ran out” question.
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode dummy;
ListNode* tail = &dummy;
while (a && b) {
if (b->val < a->val) { tail->next = b; b = b->next; }
else { tail->next = a; a = a->next; }
tail = tail->next;
}
tail->next = a ? a : b; // at most one is non-null; splice the whole remainder
return dummy.next;
}Two details worth defending. First, tail->next = a ? a : b attaches the entire remaining list in one assignment, because that remainder is already sorted and already linked. The deck writes this as a two-branch if, which is the same thing. Second, the comparison is b->val < a->val rather than a->val < b->val. On a tie this takes from a, which makes the merge stable. It does not matter for LC 21, where the nodes are indistinguishable. It matters the moment you reuse this function inside a sort, so it costs nothing to write it correctly now.
The problem says the result should be built by splicing the existing nodes. This code allocates nothing at all, which is the strongest form of that.
LC 2 — Add Two Numbers
The digits are stored least significant first, which is the convenient order: you add left to right and the carry propagates forward. The only structural decision is the loop condition.
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* tail = &dummy;
int carry = 0;
while (l1 || l2 || carry) { // carry keeps the loop alive for 99 + 1
int sum = carry;
if (l1) { sum += l1->val; l1 = l1->next; }
if (l2) { sum += l2->val; l2 = l2->next; }
carry = sum / 10;
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
return dummy.next;
}Putting carry in the loop condition removes the trailing if (carry) append(1) that the deck writes after the loop. Both are correct, because the carry out of a single digit addition is always 0 or 1, so the appended node can only ever hold 1. The three-way condition is just one fewer place to be wrong.
This is the one problem in the set where allocation is the right answer. The result is a new number, not a rearrangement of the inputs, and both inputs must survive.
Reversal is not about reversing, it is about not losing the node you are about to orphan
The reason reversal feels fiddly is that the assignment curr->next = prev destroys the only reference you had to the rest of the list. So the technique is forced: read the successor into a local before you overwrite the pointer, then rotate three variables.
LC 206 — Reverse Linked List
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* next = head->next; // save before it is destroyed
head->next = prev; // flip
prev = head; // shift the window
head = next;
}
return prev; // head is null; prev is the last node visited
}Starting prev at nullptr is what makes the empty list work without a guard: the loop never runs and prev is returned as nullptr. The deck’s version starts from the second node and needs an explicit if (head == nullptr) at the top. It is correct, and I verified it for lengths 0 through 6, but the null check is doing work that the initialiser can do for free.
The loop invariant is worth naming, because LC 92 depends on it: at the top of each iteration, prev points at the reversed prefix and head points at the untouched suffix. When the suffix is empty, the prefix is the answer.
LC 92 — Reverse Linked List II
Partial reversal needs three things the full reversal did not: the node before the range, the node after the range, and the knowledge that the first node of the range becomes its last. The sentinel supplies the first when left == 1, and the reversal loop leaves the other two sitting in variables.
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* beforeLeft = &dummy;
for (int i = 1; i < left; ++i) beforeLeft = beforeLeft->next;
ListNode* prev = nullptr;
ListNode* curr = beforeLeft->next; // first node of the range
for (int i = left; i <= right; ++i) { // exactly right - left + 1 flips
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
// prev = last node reversed = new first; curr = first node after the range
beforeLeft->next->next = curr; // old first node is now the range's tail
beforeLeft->next = prev;
return dummy.next;
}The order of those last two lines matters. beforeLeft->next still points at the old first node of the range, which is exactly the node that now needs to point at curr. Read it, use it, then overwrite it. Reverse the two lines and you lose the handle.
The deck solves this without a sentinel by tracking start = prev before the reversal and branching at the end on whether start is null. That is correct, and I checked it exhaustively for every (n, left, right) with n up to 7. It also passes through a state where the list contains a two-node cycle: after the first flip, node 1 points at node 2 and node 2 points back at node 1. Nothing traverses that region before the final fixup repairs it, so it is harmless, but it is the kind of transient corruption that makes debugging unpleasant if you stop the loop halfway. The sentinel version never enters that state.
Two pointers with a gap, because you cannot count backwards
“The nth node from the end” is a position defined relative to a boundary you have not reached yet. The obvious fix is to find the length first and then walk n minus k steps, which is two passes. The one-pass fix is to notice that a fixed distance between two pointers survives the walk: put them n apart, advance both until the leader hits the end, and the follower is n from the end by construction.
LC 19 — Remove Nth Node From End of List
This problem is listed in the deck’s contents but has no slides, which is a shame, because it is the cleanest illustration of the gap idea in the set. Note the two roles the sentinel plays here: it lets the follower stop before the doomed node, and it handles removing the head.
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0, head);
ListNode* lead = &dummy;
ListNode* trail = &dummy;
for (int i = 0; i < n; ++i) lead = lead->next; // open a gap of exactly n
while (lead->next) { // advance until lead is the last node
lead = lead->next;
trail = trail->next;
}
ListNode* doomed = trail->next; // trail is one before the target
trail->next = doomed->next;
delete doomed;
return dummy.next;
}Stopping on lead->next rather than lead is what leaves trail one short of the target instead of on it. If you loop while lead is non-null, trail lands on the node you want to delete and you have no way to unlink it. That off-by-one is the entire problem.
I tested this for every list length 1 to 8 and every valid n. The constraints guarantee 1 <= n <= size, so the opening loop cannot run off the end. If you were writing this outside the judge you would check.
LC 141 — Linked List Cycle
A hash table of visited nodes answers this in O(n) time and O(n) space and is a perfectly good first answer to give out loud. The follow-up asks for O(1) space, and the reason a speed gap works is worth stating precisely: if there is a cycle, then once both pointers are inside it, the fast pointer gains exactly one position on the slow pointer per step. A gap that shrinks by one each step and lives on a finite ring must hit zero. There is no way for fast to jump over slow.
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) { // both checks are needed: fast->next->next is two hops
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}The deck starts fast at head->next->next and compares before moving, guarded by an early return for lists shorter than two. I ran it against every list length 0 to 12 crossed with every cycle entry point and it is correct. Starting both pointers at head just removes the guard.
LC 142 — Linked List Cycle II
The deck asks the better question under the LC 141 heading: once slow and fast meet, why does walking one pointer from the head and one from the meeting point land them both on the cycle entry? That algebra is LC 142, not LC 141, and the deck’s slide derives it without writing the code. Here is the derivation with the naming made explicit.
- L is the distance from the head to the cycle entry.
- C is the length of the cycle.
- X is the distance from the cycle entry forward to the meeting point.
Slow has taken L + X steps when they meet. Fast has taken twice as many, and fast’s path is also “reach the entry, go X into the cycle, plus some whole number of extra laps”: 2(L + X) = L + X + kC for some k >= 1. Cancel and you get L + X = kC, so L = kC - X.
Read that last equation as a claim about walking. From the meeting point, the distance forward to the entry is C - X. Walking L steps from the meeting point covers kC - X, which is C - X plus k - 1 complete laps, so it lands on the entry. Meanwhile a pointer starting at the head also covers L and lands on the entry. Same number of steps, same destination, so they meet there.
ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // meeting point
ListNode* probe = head;
while (probe != slow) { // both advance one step at a time
probe = probe->next;
slow = slow->next;
}
return probe; // the cycle entry
}
}
return nullptr;
}The equality test in the second loop has to be probe != slow and not probe->next != slow->next, because when L is 0 the entry is the head itself and the loop must not run at all. I verified the return value against the known entry for every list length 0 to 12 and every cycle position.
LC 61 — Rotate List
Rotating right by k needs the length, because k can exceed the number of nodes and the real rotation is k % n. So you are paying for a counting pass regardless. The trick is to make that pass do double duty: while you are walking to the tail to count, you are also finding the node whose next you need in order to close the list into a ring. After that, rotating is just choosing where to cut.
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next) return head;
int n = 1;
ListNode* tail = head;
while (tail->next) { tail = tail->next; ++n; } // count and find the tail in one pass
tail->next = head; // close the ring
k %= n; // k can be up to 2e9
ListNode* newTail = head;
for (int i = 0; i < n - k - 1; ++i) newTail = newTail->next;
ListNode* newHead = newTail->next;
newTail->next = nullptr; // cut the ring
return newHead;
}The deck also offers the stack version: push every node, pop k of them, rebuild. It works and it is O(n) space. The ring version is O(1) space and shorter, and the deck lands on it too.
The stated constraint is 0 <= k <= 2 * 10^9, which is close enough to the 32-bit signed limit of 2,147,483,647 to be worth a second look. It fits, so int k is safe as given. I ran the rotation with k = 2000000000 against a reference implementation to confirm. If the constraint had said 4 * 10^9 you would need long long before the modulo.
When you need a map from old node to new node, the list can hold the map
LC 138 — Copy List with Random Pointer
Copying the next chain is trivial. The random pointer is not, because when you copy node A and its random points at node D, the copy of D may not exist yet, and even once it does you have no way to find it. What you need is a function from original node to copied node. A unordered_map<Node*, Node*> is that function, costs O(n) space, and is a completely reasonable answer.
The O(1) space version comes from asking where that mapping could live if not in a map. It can live in the list itself. If you splice each copy in immediately after its original, then “the copy of X” is permanently, locally addressable as X->next. No lookup, no allocation beyond the copies you were going to make anyway.
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
// 1. weave: A -> A' -> B -> B' -> C -> C' -> ...
for (Node* p = head; p; p = p->next->next) {
Node* copy = new Node(p->val);
copy->next = p->next;
p->next = copy;
}
// 2. now the copy of X is X->next, for every X, including random targets
for (Node* p = head; p; p = p->next->next)
p->next->random = p->random ? p->random->next : nullptr;
// 3. unweave, restoring the original exactly
Node* copiedHead = head->next;
for (Node* p = head; p; p = p->next) {
Node* copy = p->next;
p->next = copy->next;
copy->next = p->next ? p->next->next : nullptr;
}
return copiedHead;
}Step two is the whole idea in one line. p->random is some original node; the copy of that node is sitting directly behind it; so p->random->next is the pointer the copy needs. The null guard is for originals whose random is null.
Step three is where implementations quietly cheat. It is easy to write an unweave that produces a correct copy but leaves the original list mangled, and no judge will catch it because the judge only reads the return value. My randomized test checks both: after 3,000 trials with up to 8 nodes and random random targets, the copy is correct and every original node’s next and random are byte-for-byte what they were on entry. The deck’s unweave passes that test too.
One honest note on the space claim. This is O(1) auxiliary space, not O(1) total: you still allocate n new nodes, because the output is n new nodes. The comparison is against the hash map version, which allocates n nodes plus a map of n entries.
When the list alone is too slow, pair it with a second structure
The last two problems are the ones where pointer surgery is not enough, and recognising that is the skill being tested. A linked list is unbeatable at one thing, splicing a known node out of the middle in O(1), and hopeless at another, finding that node. So you keep the list for what it is good at and bolt on a structure that supplies the lookup.
LC 146 — LRU Cache
Follow the deck’s reasoning here, because it arrives at the answer by elimination. Keep the entries in a list ordered most recent to least recent. Inserting at one end is O(1). Evicting from the other end is O(1). Both requirements satisfied. But get(key) has to scan, which is O(n), and the problem demands O(1) average. The list cannot fix this, because scanning is what lists do.
So the missing capability is “find the node holding this key, in O(1)”. That is a hash table, keyed by the cache key, valued by a pointer or iterator into the list. The list owns the order; the map owns the lookup. Neither could do the job alone.
class LRUCache {
std::list<std::pair<int,int>> order; // front = LRU, back = MRU
std::unordered_map<int, std::list<std::pair<int,int>>::iterator> index;
std::size_t capacity;
public:
explicit LRUCache(int cap) : capacity(static_cast<std::size_t>(cap)) {}
int get(int key) {
auto it = index.find(key);
if (it == index.end()) return -1;
order.splice(order.end(), order, it->second); // move to MRU, O(1), iterator stays valid
return it->second->second;
}
void put(int key, int value) {
auto it = index.find(key);
if (it != index.end()) {
it->second->second = value;
order.splice(order.end(), order, it->second);
return;
}
if (order.size() == capacity) { // evict before inserting
index.erase(order.front().first);
order.pop_front();
}
order.emplace_back(key, value);
index[key] = std::prev(order.end());
}
};The load-bearing fact is that std::list iterators are stable. Splicing a node moves it without invalidating the iterator pointing at it, and erasing one element invalidates only that element’s iterator. That is why the map can store iterators and never needs updating when the order changes. A std::vector would invalidate everything on every insertion, which is precisely why the problem wants a list.
The deck’s version reaches the same behaviour by push_backing a fresh copy and erasing the old node on every touch. I tested it against a brute-force reference model over 3,000 randomized trials of 60 operations each and it matches exactly. It does allocate and free one list node per access, though, where splice relinks in place and allocates nothing. On a cache, which is by definition on a hot path, that difference is the point of the exercise.
LC 23 — Merge k Sorted Lists
The deck’s starting point is right: merging pairwise until one list remains is correct and slow. With k lists holding m nodes total, the first merged result gets re-traversed by every subsequent merge, so early nodes are copied through roughly k times and the total is O(mk).
The fix follows from asking what the merge actually needs at each step. It needs one thing: the smallest current head among the k lists. Repeatedly extracting the minimum from a changing set is the definition of a priority queue. Push the head of every list, and each time you pop a node, push its successor. Every node enters and leaves the heap exactly once, at O(log k) each, giving O(m log k).
ListNode* mergeKLists(std::vector<ListNode*>& lists) {
auto worse = [](ListNode* a, ListNode* b) { return a->val > b->val; }; // > gives a MIN-heap
std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(worse)> pq(worse);
for (ListNode* node : lists)
if (node) pq.push(node); // skip empty lists; [] and [[]] both yield an empty heap
ListNode dummy;
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* node = pq.top();
pq.pop();
tail->next = node;
tail = node;
if (node->next) pq.push(node->next);
}
return dummy.next;
}std::priority_queue is a max-heap by default, so the comparator returns true when the first argument should be treated as lower priority. Writing a->val > b->val inverts it into a min-heap. Getting this backwards produces a descending list and is the most common bug in this problem.
You do not need to null-terminate the result. The last node popped from the heap must be one whose next is null, because any successor would have been pushed and the heap would not be empty. I instrumented the loop to confirm it across 500 randomized cases. Writing tail->next = nullptr anyway is harmless and some reviewers will prefer it.
The misfits: three problems that look like pointer puzzles and are not
Every problem set has entries that are filed under a topic because of the data type in the signature rather than the technique in the solution. Recognising them early saves you from reaching for a tool that will not fit.
LC 426 — Convert BST to Sorted Doubly Linked List (Premium)
The output is a circular doubly linked list, so it lands in the linked list bucket. But no linked list technique appears in the solution. The real question is “how do you visit a BST’s nodes in ascending order”, and the answer is inorder traversal, which is a tree pattern. The list is just the shape you write the visit order into.
Once you see that, the implementation is an inorder walk that remembers the previously visited node and links it to the current one. The tree’s left and right become predecessor and successor, which the problem statement spells out.
void inorder(Node* node, Node*& first, Node*& last) {
if (!node) return;
inorder(node->left, first, last);
if (!first) first = node; // leftmost node visited becomes the head
node->left = last; // left = predecessor
if (last) last->right = node; // right = successor
last = node;
inorder(node->right, first, last);
}
Node* treeToDoublyList(Node* root) {
if (!root) return nullptr;
Node* first = nullptr;
Node* last = nullptr;
inorder(root, first, last);
first->left = last; // close the circle
last->right = first;
return first;
}Overwriting node->left mid-traversal is safe, and it is the detail that makes people nervous. By the time that line runs, the left subtree has already been fully visited and relinked, so nothing will read the original pointer again. The recursion into node->right happens after, and right has not been touched yet.
The deck passes first and last as Node**. Passing them as Node*& is the same thing with less punctuation. I checked the output on 2,000 random BSTs of up to 12 nodes: forward through right is sorted ascending and wraps to the head, backward through left is sorted descending and wraps too.
LC 708 — Insert into a Sorted Circular Linked List (Premium)
This one is not a technique problem either. There is no clever pointer manipulation available; the insert itself is two assignments. What the problem tests is whether you can enumerate the cases without missing one, which is why the deck spends its whole slide asking “what are the possible cases?” rather than showing an algorithm.
Walk the ring one adjacent pair at a time. Exactly three situations can justify inserting between prev and curr:
- An ordinary gap.
prev->val <= insertVal <= curr->val. Inserting 2 into 1,3,5,7,9 lands here. - The wrap point, as a new maximum.
prev->val > curr->valis how you detect the one descent in the ring, andinsertVal >= prev->valmeans the value belongs at the top. Inserting 10 into 1,3,5,7,9. - The wrap point, as a new minimum. Same descent, but
insertVal <= curr->val. Inserting 0 into 1,3,5,7,9.
Then there is the case that breaks naive solutions: every value in the list is identical. There is no descent to find and no gap that contains the new value, so none of the three conditions ever fires and the loop completes a full lap. Inserting anywhere is correct, so the answer is to let the loop terminate and insert wherever it stopped.
Node* insert(Node* head, int insertVal) {
Node* node = new Node(insertVal);
if (!head) { node->next = node; return node; } // single-node circular list
Node* prev = head;
Node* curr = head->next; // curr == prev when size is 1
do {
if (prev->val <= insertVal && insertVal <= curr->val) break; // ordinary gap
if (prev->val > curr->val && // the one descent
(insertVal >= prev->val || insertVal <= curr->val)) break; // new max or new min
prev = curr;
curr = curr->next;
} while (prev != head);
// fallthrough after a full lap: all values equal, so any gap is a valid gap
node->next = curr;
prev->next = node;
return head; // return the node we were given
}The do while is deliberate. A while loop testing prev != head up front would exit immediately, since prev starts at head. And the loop must terminate on prev returning to head, not on curr, so that every adjacent pair including the wrap pair gets examined exactly once.
I tested this against eight list shapes, including {2,2,2,2} and {7,7,7}, crossed with every choice of which node is the given head and every insert value from -3 to 12. After each insert the result is still circular, contains exactly the original multiset plus the new value, and has at most one descent going around. The deck’s version passes the same suite.
LC 707 — Design Linked List
Nothing here is algorithmically interesting, which is the point. The exercise is whether you can honour a written contract: what does get return for a negative index, what does addAtIndex do when the index equals the size versus exceeds it, is the list zero-indexed. It is also the one problem in the set where a sentinel head is not an optimisation but a structural decision, since it makes addAtIndex(0) and deleteAtIndex(0) ordinary cases.
class MyLinkedList {
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {} // initialise BOTH members
};
Node* head; // permanent sentinel; head->next is element 0
int size;
public:
MyLinkedList() : head(new Node(0)), size(0) {}
~MyLinkedList() { Node* p = head; while (p) { Node* t = p->next; delete p; p = t; } }
int get(int index) {
if (index < 0 || index >= size) return -1;
Node* p = head->next;
for (int i = 0; i < index; ++i) p = p->next;
return p->val;
}
void addAtHead(int val) { addAtIndex(0, val); }
void addAtTail(int val) { addAtIndex(size, val); }
void addAtIndex(int index, int val) {
if (index < 0 || index > size) return; // index == size appends; beyond that, ignore
Node* before = head;
for (int i = 0; i < index; ++i) before = before->next;
Node* node = new Node(val);
node->next = before->next;
before->next = node;
++size;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node* before = head;
for (int i = 0; i < index; ++i) before = before->next;
Node* doomed = before->next;
before->next = doomed->next;
delete doomed;
--size;
}
};I ran this against a std::vector reference model, 3,000 trials of 40 random operations, and it matches on every call. The destructor runs clean under AddressSanitizer. That destructor is not decoration, and the next section explains why.
Edge cases and traps, including two real bugs in the source deck
This is the section that pays for the post. Everything below was reproduced on a compiler, not recalled.
The uninitialised next in LC 707
The deck’s node type is declared like this:
struct Node {
int val;
Node* next;
Node(int _val) : val(_val) {} // next is never initialised
};That constructor leaves next holding whatever was in that memory. The solution is accepted anyway, and the reason is subtle: every loop in the class is bounded by the size counter rather than by a null check, so the indeterminate pointer is copied around but never dereferenced. The code is one refactor away from a crash, and it reads an indeterminate value on essentially every call, which is undefined behaviour regardless of whether it happens to work.
AddressSanitizer will not flag this, because it tracks memory validity rather than initialisation. To make it visible I overrode operator new to fill fresh allocations with 0xCD, the way a debug allocator does, and then added the loop anyone writes next — a destructor, a print(), a toVector() — the kind that walks until it hits null:
// with poisoned allocations:
get(1) = 2 // spec says 2 -> passes
get(1) = 3 // spec says 3 -> passes
last node's next is 0xcdcdcdcdcdcdcdcd // never null-terminated
now the pointer-bounded traversal:
Bus error // exit code 135The fix is four characters: Node(int v) : val(v), next(nullptr) {}. If you write linked list nodes by hand in an interview, initialise every pointer member in the constructor. The judge will not catch it and neither will your first three test cases.
The priority queue that only compiles under C++20
The deck’s LC 23 declares the heap like this:
auto compare = [](ListNode* lhs, ListNode* rhs) { return lhs->val > rhs->val; };
std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(compare)> pq; // no argumentThat default-constructs the comparator. Before C++20, a lambda’s closure type had no default constructor, so this does not compile. C++20 gave captureless lambdas a default constructor, and since LeetCode compiles C++20 the submission is accepted. Compiled locally with -std=c++17, the same file fails:
error: no matching function for call to
'std::priority_queue<ListNode*, std::vector<ListNode*>,
mergeKLists(std::vector<ListNode*>&)::<lambda(ListNode*, ListNode*)> >::priority_queue()'Passing the comparator explicitly, pq(worse), compiles under both standards and costs nothing. Worth knowing if you ever paste an accepted solution into a real codebase that has not moved to C++20.
The heap holds k entries, not log k
The deck states the space complexity of the priority queue in LC 23 as O(log n). It is O(k), where k is the number of lists: at any moment the heap holds at most one node per list, since a successor is only pushed when its predecessor is popped. The log belongs to the time per push and pop, not the size. I instrumented the loop over 500 randomized cases with up to 8 lists and the heap never exceeded k entries.
The output is not auxiliary space either, since the merged list reuses the input nodes rather than allocating. So the honest summary is O(m log k) time, O(k) auxiliary space.
Leaked sentinels and signed comparisons
- Heap-allocated dummies.
new ListNode(-1)as a sentinel leaks one node per call in LC 21, LC 2 and LC 23. LeakSanitizer reported 4,000 leaked nodes from 4,000 calls to the deck’smergeTwoLists. A stackListNode dummy;is the same code with no leak. q.size() > maxCapacityin the LRU cache compares astd::size_tagainst anint, which triggers-Wsign-compare. The constraints guaranteecapacity >= 1so it cannot misbehave here, but storing the capacity asstd::size_tremoves the warning and the class of bug.- Unused locals. The deck’s LC 21 declares
ListNode* node = nullptr;inside the loop and never uses it. Harmless, but it is the kind of thing an interviewer will ask about, and you will have to admit you do not know why it is there.
The small edge cases each problem hides
| Problem | The case that breaks a first draft |
|---|---|
| 21 | One or both lists empty. The tail->next = a ? a : b line covers it; a two-branch version must handle both branches. |
| 2 | [9,9,9] + [1], where the carry propagates past the end of both inputs and the result is longer than either. |
| 19 | Removing the head, when n equals the length. Without a sentinel there is no trail to stop at. |
| 141 | A single node pointing at itself. Also a list of length 2 with no cycle, where fast->next must be checked before the second hop. |
| 142 | L = 0, when the head is the cycle entry. The second loop must be able to run zero times. |
| 61 | k larger than the length, and k % n == 0, which must return the list unchanged rather than cutting in the wrong place. |
| 92 | left == 1, so the reversal changes the head. This is the case the sentinel exists for. |
| 138 | A node whose random is null, and a node whose random points at itself. |
| 146 | put on an existing key must count as a use and must not evict. Evicting before inserting matters when capacity is 1. |
| 23 | lists empty, and lists containing null pointers for empty lists. Both must yield null, not a crash. |
| 426 | Empty tree returns null. A single node must point at itself in both directions. |
| 708 | Every value identical, so no insertion point is ever found and the loop laps the whole ring. |
| 707 | addAtIndex with index equal to size appends; greater than size does nothing. Not the same rule as get. |
The six techniques, one table
| Missing fact | Technique | Cost | Problems |
|---|---|---|---|
| A position before the head | Sentinel node on the stack | O(1) | 21, 2, 19, 92, 23, 707 |
| The previous node | Carry prev beside curr | O(1) | 206, 92, 708 |
| Distance from the end | Two pointers a fixed gap apart | O(1), one pass | 19 |
| Whether the walk terminates | Two pointers at different speeds | O(1) | 141, 142 |
| The length | Close the list into a ring, then cut | O(1) | 61 |
| Old node to new node | Weave copies into the original | O(1) auxiliary | 138 |
| O(1) lookup into the middle | Pair the list with a hash map | O(n) | 146 |
| The minimum across k heads | Pair the list with a min-heap | O(k) | 23 |
When you meet a linked list problem you have not seen, the useful first question is not “which algorithm is this”. It is “what does this problem need to know that a node cannot tell it”. The answer picks the technique for you, and the table above has eight of them.
Source and method
The problem selection and the framing of several solutions come from a linked list session deck by Joseph Choi. LC 19 appears in that deck’s table of contents without slides, and LC 142 is derived there under the LC 141 heading without code; the implementations for both are mine.
Every C++ snippet in this post was compiled with g++ -std=c++20 -Wall -Wextra and run under -fsanitize=undefined,address with leak detection enabled. Correctness was checked exhaustively where the input space is small (all list lengths up to 12 crossed with all cycle positions for 141 and 142; all valid (n, left, right) triples for 92) and by randomized differential testing against reference models everywhere else (146 against a brute-force cache, 707 against a std::vector, 138 against a full structural comparison that also verifies the original list is restored). Claims about the deck’s code, including both bugs above, were reproduced rather than inferred.