RE-ROUTING THE ARROWS
YOUR CALL
Before a single interview problem, own the object itself: a node holding a value and a pointer to the next one. This deck builds the linked list from nothing — traverse it, insert and delete anywhere, then add a second pointer for the doubly linked list and reverse it. Every operation is re-routing arrows, animated one pointer at a time, and the capstone is building the whole structure yourself.
This is not a list of problems. It is 4 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
1 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
A linked list is a bet: pay O(n) access to win O(1) middle-mutation. These cards are the signals in a statement that say the bet is worth taking — and which flavour of list to reach for.
a linked list splices in O(1) once you hold the spot; an array shifts O(n)
LINKED LIST — pointer surgery, no shiftinginsert/delete O(1) given the nodea list has no indices — reaching node k costs a full walk
ARRAY — contiguous, O(1) random accesslist access is O(k)with only next you cannot reach prev; a doubly list can
DOUBLY LINKED LIST — unlink via node->prevO(1) delete given the nodehead and tail pointers make both ends O(1)
DOUBLY LIST with head + tailpush/pop front and back O(1)special-casing head is where off-by-one bugs live
A DUMMY HEAD node — every position is uniformremoves the head special casea list grows one node at a time without reallocation
LINKED LIST — allocate as you goO(1) growth, O(n) cache-unfriendlyThe whole cost model of a linked list on one screen. It is not about n so much as about which operation — indexing is dear, splicing is cheap.
GOLD ROWS ARE WHERE LISTS BEAT ARRAYS · ACCESS-BY-INDEX IS THE ONE THING THEY GIVE UP
Four fundamentals, one object. Traverse it, mutate it, add a second pointer, reverse it — then build the whole thing yourself. The interview problems are decks 2 and 3.
What is the one operation an array does in O(1) that a linked list cannot?
Random access. An array stores elements contiguously, so element k is a single address computation — O(1). A linked list scatters nodes in memory and connects them only by pointers, so the only way to reach node k is to start at head and follow next k times — O(k). That single trade explains everything: lists win when you splice in the middle a lot and never index; arrays win when you index a lot. Binary search, for instance, is pointless on a list because you cannot jump to the middle.
A singly linked list node holds a value and a next pointer. What does the last node's next point to, and why does it matter?
null. The tail's next is null, and that is precisely what stops a traversal — while (temp != nullptr) temp = temp->next walks until it falls off the end. Get this wrong (a dangling pointer, or a self-reference) and the walk either crashes or loops forever. Half of all linked-list bugs are a null that was not checked or not set: dereferencing temp->next when temp is already null is the single most common crash.
Why do so many linked-list solutions start by creating a dummy (sentinel) head node?
It erases the head special case. Without a dummy, inserting or deleting at position 0 has to update head itself, so you write a separate branch — and that branch is where off-by-one and null bugs breed. A dummy node sitting before the first real node means every position, including the front, has a genuine prev to splice against; you return dummy->next at the end. One uniform code path instead of two is why it appears in Design Linked List, Remove Nth Node, Merge, and half of deck 2.
A linked list is the simplest pointer structure: a chain of nodes, each holding a value and a next pointer to the following node, ending when next is null. There are no indices — the only handle you get is head, and everything (length, search, printing) is one traversal: start at head and follow next until null, doing your work at each node.
HOW DO YOU DO ANYTHING TO A LIST YOU CAN ONLY ENTER FROM ITS head?
To compute the length of a singly linked list, what is the loop, and where does it stop?
Walk until temp itself is null. Starting at head and looping while (temp != nullptr), you count each node and advance; the loop naturally ends when temp steps past the tail to null. The common off-by-one is stopping at temp->next != null, which never counts the last node. The condition is on temp, not temp->next — that distinction is the whole difference between a correct length and one that is short by one.
On the list 8 → 3 → 7 → 2 → null, searching for 7 with a traversal, how many nodes does temp visit before it finds it?
Three visits. temp starts at node 0 (value 8), moves to node 1 (value 3), then node 2 (value 7) where the match is found — the third node examined, at index 2. There is no shortcut: search on a linked list is inherently linear because you cannot binary-search a structure you can only walk forward one node at a time. The MECHANISM slide animates temp hopping node to node until the value lights up.
Why can't you binary-search a sorted linked list in O(log n), the way you would a sorted array?
Finding the middle is O(n), so the log-n advantage evaporates. Binary search's power comes from jumping to a[mid] in O(1); on a list, locating that midpoint means walking half the nodes, and you would pay O(n) at every level for a total of O(n log n) — worse than a plain O(n) scan. This is the deepest consequence of “no random access”: entire algorithm families (binary search, quickselect) simply do not port to lists, which is why list problems lean on pointers — fast/slow, dummy, reverse — instead.
Everything in this topic is built on a single loop: point temp at the head and follow temp = temp->next until it becomes null, doing your work at each node. Length is a counter, search is a comparison, printing is a read. There is no random access — you cannot jump to node k, you must walk to it — which is the whole trade linked lists make versus arrays.
Insertion and deletion are why linked lists exist: both are O(1) pointer surgery once you hold the right spot, with no shifting. To insert, walk prev to the node before the gap, then new->next = prev->next before prev->next = new. To delete, bypass the victim with prev->next = victim->next and free it. A dummy head makes position 0 behave like any other.
HOW DO YOU ADD OR REMOVE A NODE ANYWHERE WITHOUT SHIFTING THE REST?
This insertion at a middle position loses part of the list. Which line ordering is wrong?
Node* node = new Node(val); prev->next = node; node->next = prev->next; // too late — prev->next is now node
The two assignments are in the wrong order. Setting prev->next = node first overwrites the link to the rest of the list; then node->next = prev->next reads the value you just changed, so node ends up pointing at itself and everything after the insertion point is orphaned. The rule is absolute: link the new node outward first (node->next = prev->next), then relink prev. Order is the entire difficulty of pointer surgery.
After prev->next = victim->next deletes a node from a singly list in C++, what must you not forget?
delete victim. Re-pointing prev->next makes the victim unreachable from the list, but the object still occupies heap memory until you explicitly free it — a leak in C++. Capture the pointer (victim = prev->next) before the bypass so you still have a handle to delete. Languages with garbage collection (Java, Python) reclaim it automatically, but the interviewer asking in C++ is testing exactly this discipline.
How does a dummy head node simplify deleteAtIndex(0) — removing the first real node?
The dummy gives position 0 a real predecessor. Without it, deleting the first node means special-casing head = head->next and propagating the new head; with a dummy sentinel in front, prev for index 0 is simply the dummy, so prev->next = victim->next handles the front exactly like the middle. You return dummy->next as the real head at the end. One code path for every index is why Design Linked List and so many deck-2 problems open with Node* dummy = new Node().
Insertion is pure pointer surgery and the order of two assignments is the whole game. Walk prev to the node just before the gap, then new->next = prev->next first, and only then prev->next = new. Reverse those two and you overwrite the link to the rest of the list before the new node has grabbed it — losing everything after the insertion point. A dummy head node removes the “insert at position 0” special case.
Deletion is insertion's mirror: walk prev to the node before the target, remember victim = prev->next, then prev->next = victim->next to route the arrow around it. In C++ you then delete victim to free the memory — forgetting it leaks. Once the arrow jumps over the victim, nothing points to it, so it is unreachable; the dummy head again saves you from special-casing deletion of the first node.
“Design / implement a linked list” with get, addAtHead, addAtTail, addAtIndex and deleteAtIndex. It is the capstone of the fundamentals: every operation is a traversal plus a splice, and a dummy head makes all of them uniform.
Keep a dummy head and a size counter. get(i) walks i steps past the dummy. addAtIndex(i) and deleteAtIndex(i) both walk prev to the node at index i − 1 (starting from the dummy, so index 0 is not special) and then splice or bypass. addAtHead / addAtTail are just addAtIndex(0) and addAtIndex(size).
// A dummy head makes every index — including 0 — a uniform splice. class MyLinkedList { struct Node { int val; Node* next; Node(int v): val(v), next(nullptr) {} }; Node* dummy; int sz; public: MyLinkedList(): dummy(new Node(0)), sz(0) {} int get(int index) { if (index < 0 || index >= sz) return -1; Node* cur = dummy->next; while (index--) cur = cur->next; // walk index steps return cur->val; } void addAtHead(int val) { addAtIndex(0, val); } void addAtTail(int val) { addAtIndex(sz, val); } void addAtIndex(int index, int val) { if (index < 0 || index > sz) return; Node* prev = dummy; while (index--) prev = prev->next; // stop prev at index-1 Node* node = new Node(val); node->next = prev->next; // link OUT first prev->next = node; // then relink prev sz++; } void deleteAtIndex(int index) { if (index < 0 || index >= sz) return; Node* prev = dummy; while (index--) prev = prev->next; Node* victim = prev->next; prev->next = victim->next; // bypass delete victim; // free sz--; } };
// A dummy head makes every index - including 0 - a uniform splice. class MyLinkedList { private static class Node { int val; Node next; Node(int v) { val = v; } } private Node dummy = new Node(0); private int sz = 0; public int get(int index) { if (index < 0 || index >= sz) return -1; Node cur = dummy.next; while (index-- > 0) cur = cur.next; // walk index steps return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(sz, val); } public void addAtIndex(int index, int val) { if (index < 0 || index > sz) return; Node prev = dummy; while (index-- > 0) prev = prev.next; // stop prev at index-1 Node node = new Node(val); node.next = prev.next; // link OUT first prev.next = node; // then relink prev sz++; } public void deleteAtIndex(int index) { if (index < 0 || index >= sz) return; Node prev = dummy; while (index-- > 0) prev = prev.next; prev.next = prev.next.next; // bypass; GC frees it sz--; } }
# A dummy head makes every index — including 0 — a uniform splice. class Node: def __init__(self, val): self.val = val self.next = None class MyLinkedList: def __init__(self): self.dummy = Node(0) self.size = 0 def get(self, index): if index < 0 or index >= self.size: return -1 cur = self.dummy.next for _ in range(index): cur = cur.next return cur.val def addAtHead(self, val): self.addAtIndex(0, val) def addAtTail(self, val): self.addAtIndex(self.size, val) def addAtIndex(self, index, val): if index < 0 or index > self.size: return prev = self.dummy for _ in range(index): # stop prev at index-1 prev = prev.next node = Node(val) node.next = prev.next # link OUT first prev.next = node # then relink prev self.size += 1 def deleteAtIndex(self, index): if index < 0 or index >= self.size: return prev = self.dummy for _ in range(index): prev = prev.next prev.next = prev.next.next # bypass (GC frees it) self.size -= 1
Off-by-one on where prev stops, and missing bounds checks. Because the walk starts at the dummy, looping index times lands prev at index i − 1 — exactly where you splice; starting from the real head instead shifts everything by one. And addAtIndex permits index == size (append) while get and deleteAtIndex require index < size — mixing up the two boundary conditions is the most common way this passes the samples and fails the edge tests.
The walkthrough for #01 Design Linked List. Watch it, then go straight back and write it yourself.
A doubly linked list adds a second pointer, prev, to every node, so each node knows both neighbours. That buys two things a singly list cannot do: O(1) deletion of a node you already hold (you can reach its prev), and clean backward traversal. The cost is one extra pointer per node and the discipline of maintaining four links on every insert.
WHAT DOES A SECOND POINTER PER NODE BUY, AND WHAT DOES IT COST?
Inserting a node between prev and cur in a doubly linked list sets how many pointers, and which?
Four links. The new node needs both of its own pointers set (new->next = cur, new->prev = prev) and both neighbours must point back to it (prev->next = new, cur->prev = new). Set the new node's two links first, then relink the neighbours. Miss any one — most often a prev back-link — and the list is subtly corrupt: forward iteration works, backward iteration walks into a hole. The MECHANISM slide highlights all four re-routes in order.
Why can a doubly linked list delete a node handed to you in O(1), while a singly list needs O(n)?
The back-pointer gives you prev for free. Deleting a node means prev->next = node->next, so you need prev. A doubly node already stores it (node->prev), making the unlink O(1) — node->prev->next = node->next; node->next->prev = node->prev. A singly node has no way back, so finding prev means re-walking from head, which is O(n). This single capability is why LRU/LFU caches and browser-history structures are built on doubly lists.
A doubly linked list adds a prev pointer, so every node can look both ways — which buys O(1) deletion given the node and a clean reverse, at the cost of one more pointer per node. Insertion now touches four links: new->next, new->prev, prev->next, and cur->prev. Miss a back-link and the forward walk still looks perfect while the reverse walk quietly breaks — the classic doubly-list bug.
Reversing a doubly linked list is the payoff of the prev pointer. Since each node already knows both neighbours, reversal is just: walk once and swap every node's prev and next. After the pass, every arrow has flipped, so the old tail — the node that had no next — now has no prev, making it the new head. O(n) time, O(1) space, no new nodes.
HOW DO YOU REVERSE A LIST WITHOUT MOVING A SINGLE NODE IN MEMORY?
The core step of reversing a doubly linked list, at each node, is:
Swap the node's two pointers. Because a doubly node holds both prev and next, reversing the whole list is nothing more than exchanging those two fields at every node — no allocation, no data movement. The only subtlety is advancing: after the swap, the direction you want to go (the old next) now lives in node->prev, so you step with node = node->prev. It is one of the most elegant O(1)-space operations in the topic.
Reversing 5 ⇄ 8 ⇄ 12 ⇄ 20, which node becomes the new head, and why?
20, the old tail. Before reversal, 20 is the tail: it has a prev (12) but no next. After swapping every node's pointers, that relationship inverts — 20 now has a next (12) but no prev, and “no prev” is exactly what makes a node the head. Returning the old head (5) instead of the new one is the classic mistake; 5 has become the tail. The MECHANISM slide moves the head and tail labels to opposite ends at the final step.
Because a doubly node already knows both neighbours, reversing it is startlingly simple: walk once and swap(node->prev, node->next) at each node. After the pass every arrow has flipped, so the node that used to have no next (the tail) now has no prev — which is exactly what head means. Return the old tail. O(n) time, O(1) space, no new nodes.
You are storing a playlist where users constantly insert and remove songs in the middle, and you never need to jump to “song number 500”. Array or linked list?
Linked list. The access pattern is all middle-mutation and no indexing, which is exactly the list's sweet spot: splicing a node in or out is a couple of pointer writes, while an array would shift every later element on each edit — O(n) per operation. Flip the requirement to “jump to song 500 constantly” and the answer flips to array. Matching the data structure to the operation mix, not to habit, is the actual skill this deck is building toward.
A doubly linked list costs one extra pointer per node over a singly list. What two capabilities does that buy?
O(1) delete-given-a-node and two-way traversal. The extra prev pointer means a node knows its predecessor, so you can unlink it without walking from the head to find prev — impossible in a singly list, where deleting a handed-in node is O(n). It also lets you iterate backward and reverse by a simple prev/next swap. The cost is the extra pointer's memory and the discipline of maintaining both link directions on every edit — which is why the LRU cache (deck 3) is built on a doubly list.
Pointer bugs do not throw at the line you wrote them — they surface later, on an edge case, as a lost tail or a broken back-chain. Every one of these compiles.
On insertion you must set new->next = prev->next first, then prev->next = new. Do it the other way and you overwrite the only link to the rest of the list before the new node has grabbed it — everything after the insert point is lost.
temp->next when temp is already null crashes. Empty lists, single-node lists and the tail are the edge cases; always test the loop on a 0- and 1-node list before trusting it.
Bypassing a node with prev->next = victim->next unlinks it but does not free it. In C++ you must delete victim; forgetting it is a memory leak the judge may not catch but an interviewer will.
Insertion/deletion in a doubly list touches links in both directions. Set the next chain but forget a prev, and the forward walk looks perfect while the reverse walk is silently broken — a bug that hides until someone iterates backward.
When an operation can change the first node (insert/delete at position 0), the new head must be propagated back to the caller. A local reassignment that never returns leaves the caller pointing at a stale or freed node. The dummy-head pattern sidesteps this.
To insert/delete at position k you stop prev at k − 1, not k. Looping k times from the dummy versus from the real head shifts everything by one — check whether your start node is the dummy or the first real node.
The cost of every operation, once. The right-hand column is when to reach for it — and the O(k) rows are the price of having no indices.
Once nodes and pointers are automatic — traverse, splice, bypass, swap — the interview problems stop being about linked lists and start being about which pointer trick (fast/slow, dummy, reverse) the statement is quietly asking for. That is decks 2 and 3.
Lectures are Striver's A2Z linked-list playlist (L1–L4). The single sheet problem here is Design Linked List; the medium and hard problems are decks 2 and 3.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.