RE-ROUTING THE ARROWS
YOUR CALL
Almost every medium linked-list problem is one of a handful of pointer tricks: a slow pointer and a fast one, a three-pointer reversal, Floyd's tortoise-and-hare for cycles, two pointers held a fixed gap apart, a rearrange-and-stitch, or a tandem walk of two lists. Learn the six and the ten problems collapse into variations you can write from memory — each animated one pointer at a time, with the trap that catches most people called out.
This is not a list of problems. It is 10 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
10 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.
Ten problems, six tricks. The cards below are the phrases in a statement that pick the trick for you — hearing which one a problem is asking for is the whole skill.
one pointer at double speed reaches the end as the other reaches the middle
FAST & SLOW pointersO(n) time · O(1) spaceflipping next-pointers in place is the engine; palindrome composes it
THREE-POINTER REVERSE (prev / curr / next)O(n) time · O(1) spacea hash set works but costs O(n) space; two speeds cost nothing
FLOYD'S TORTOISE & HAREO(n) time · O(1) spaceyou cannot index from the end — manufacture a fixed gap instead
TWO POINTERS, GAP OF n (+ dummy head)O(n) one pass · O(1) spacesplit into separate chains as you walk, then stitch them back
REARRANGE & STITCH (odd/even, segregate)O(n) time · O(1) spacewalk them in tandem, building the answer behind a dummy head
TANDEM WALK + DUMMY NODEO(n+m) time · O(1) spaceEvery one of these runs in O(n) time; the game is O(1) space — trading a hash set or an array for a couple of pointers. The gold rows are the pointer methods this deck teaches.
TIME IS O(n) FOR ALL · THE WIN IS SPACE · POINTERS BEAT AN ARRAY OR A HASH SET
Ten mediums, six tricks. Fast/slow, reverse, and Floyd are the load-bearing three; the gap, the rearrange, and the tandem walk finish the set. The hards (deck 3) compose these.
Why does a fast pointer (2 steps) and a slow pointer (1 step), both from the head, leave slow at the middle when fast reaches the end?
Double speed means half the distance. In the same number of steps, fast moves 2k nodes while slow moves k; when fast has traversed all n nodes, k = n/2, so slow sits at the midpoint. No length count, no second pass. The only subtlety is the loop guard — fast && fast->next versus fast->next && fast->next->next — which decides whether an even-length list gives you the first or second middle.
This in-place reversal returns a list of length 1. Which line is missing or misplaced?
while (curr) { curr->next = prev; // flipped before saving next! prev = curr; curr = curr->next; // curr->next is now prev… }
You must save next before you flip. The instant curr->next = prev runs, the forward link is gone, so the later curr = curr->next follows the pointer you just redirected — straight back to prev — and the walk collapses. The fix is the first line of the dance: ListNode* next = curr->next; then flip, then advance prev = curr; curr = next;. Every reverse-based problem in this deck depends on that ordering.
Cycle detection with a hash set of visited nodes is O(n) time. What does Floyd's tortoise-and-hare buy over it?
O(1) space instead of O(n). Both approaches are linear in time, but the hash set stores every node it has seen; Floyd's method carries only two pointers. A fast pointer moving two steps and a slow one moving one will, inside any loop, close the gap by one node per step until they collide — a meeting that is impossible on a null-terminated list. Interviewers ask for the O(1) solution specifically because the hash set is the obvious one; the tortoise and hare is the one that shows you know the pointer trick.
The fast & slow pattern: two pointers from the head, one moving one node per step and one moving two. Because fast covers twice the ground, the moment it runs off the end slow is standing on the middle — the whole list halved in a single pass, no length count, O(1) space.
HOW DO YOU FIND THE MIDDLE IN ONE PASS, WITHOUT COUNTING THE LENGTH?
Why is the loop condition while (fast && fast->next) rather than just while (fast)?
The double step reads fast->next->next. Evaluating that requires fast to be non-null and fast->next to be non-null; on an even-length list fast can land exactly on the last node, where fast->next is null and the second hop would dereference it. Guarding both is what keeps the fast pointer safe, and the precise guard you choose also controls which of the two middles you get.
On 1 → 2 → 3 → 4 → 5, after the fast/slow loop, where is slow?
Value 3, index 2. Trace it: slow 1→2→3 while fast 1→3→5. When fast is on 5, fast->next is null, the loop stops, and slow is on 3 — dead centre of the five nodes. For an even list like 1→2→3→4 the same guard leaves slow on 3 (the second middle); switching the guard would give 2. The MECHANISM slide steps the two pointers and pulses the middle when it settles.
Send slow one node at a time and fast two. Because fast covers exactly double the distance, when it runs off the end slow has covered half — it is standing on the middle, found in a single pass with no length count. The loop guard fast && fast->next is what keeps the double-step from dereferencing null, and choosing that guard (versus fast->next && fast->next->next) decides which node you get on an even-length list.
“Return the middle node” (or split the list in half). Anything asking for the midpoint of a singly list in one pass is the fast/slow pattern — no length count, O(1) space.
Two pointers from the head; fast moves two nodes for every one that slow moves. When fast falls off the end, slow is exactly halfway. For even length, the guard fast && fast->next returns the second of the two middles (LeetCode's choice).
// Fast covers 2x the distance, so when it hits the end slow is halfway. ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; // +1 fast = fast->next->next; // +2 } return slow; // the (second) middle }
// Fast covers 2x the distance, so when it hits the end slow is halfway. public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; // +1 fast = fast.next.next; // +2 } return slow; // the (second) middle }
# Fast covers 2x the distance, so when it hits the end slow is halfway. def middleNode(head): slow = fast = head while fast and fast.next: slow = slow.next # +1 fast = fast.next.next # +2 return slow # the (second) middle
The null guard, and which middle you return. fast->next->next dereferences fast->next, so both fast and fast->next must be checked or an even-length list crashes. That same guard determines whether you land on the first or second middle — problems built on this (delete-middle, reorder) care which, so know your convention.
The walkthrough for #01 Middle of the Linked List. Watch it, then go straight back and write it yourself.
Reversing a singly linked list in place is the three-pointer dance that half the hard problems reuse. Carry prev (starts null), curr, and a temporary next. Each step: save next, point curr->next back at prev, then slide all three forward. prev ends on the old tail — the new head.
HOW DO YOU FLIP EVERY POINTER WITHOUT LOSING THE REST OF THE LIST?
In the three-pointer reversal, what is returned at the end, and why?
Return prev. As curr advances, prev trails one behind, and when curr falls off the end to null, prev is sitting on the last real node — the old tail, which in the reversed list is the head. The original head variable now points at what became the tail, so returning it yields a truncated list. This “return prev” is the single most common slip in reversal-based problems.
Reverse-nodes-in-k-group and reorder-list are “hard” problems. What makes them tractable once this unit is automatic?
They are sublist reversals with reconnection. Reverse-in-k-group runs this dance on each window of k nodes and links the reversed chunks together; reorder-list reverses the back half and interleaves. The core loop is identical — save, flip, slide — and the only new work is tracking the boundary nodes so the reversed segment stitches back cleanly. That is exactly why reversal is taught as a fundamental: the deck-3 hards are compositions of it.
Reversing a singly list in place is the dance every hard problem reuses. Hold prev (starts null), curr, and a saved next. Each step: save next = curr->next, flip curr->next = prev, then slide prev = curr; curr = next. Miss the save and you lose the rest of the list the instant you flip. prev walks to the old tail and is the new head — return it, not the old head.
“Reverse the list” — the most reused operation in the topic. Iterative three-pointer walk in O(1) space; the recursive form is the same flip unwound from the tail.
Hold prev (null), curr (head), and a temporary next. Each step: save next = curr->next, flip curr->next = prev, then slide prev = curr; curr = next. prev ends on the old tail — return it.
// Save next, flip curr->next to prev, slide all three forward. ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; // save the rest FIRST curr->next = prev; // flip the link prev = curr; // slide prev curr = next; // slide curr } return prev; // old tail is the new head }
// Save next, flip curr.next to prev, slide all three forward. public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // save the rest FIRST curr.next = prev; // flip the link prev = curr; // slide prev curr = next; // slide curr } return prev; // old tail is the new head }
# Save next, flip curr.next to prev, slide all three forward. def reverseList(head): prev, curr = None, head while curr: nxt = curr.next # save the rest FIRST curr.next = prev # flip the link prev = curr # slide prev curr = nxt # slide curr return prev # old tail is the new head
Flipping before saving, or returning the old head. If you set curr->next = prev before capturing next, the forward link is gone and the walk collapses. And the answer is prev — it reached the old tail (the new head); returning the original head yields a single node.
The walkthrough for #02 Reverse Linked List. Watch it, then go straight back and write it yourself.
Floyd's tortoise and hare detects a cycle with two pointers and no extra memory. Run slow one step and fast two. On a null-terminated list fast simply reaches the end; but if there is a loop, fast enters it and gains one node on slow every step, so it eventually laps and collides with it. A meeting is proof of a cycle.
HOW DO YOU DETECT A LOOP IN O(1) SPACE, WITHOUT A SET OF VISITED NODES?
Why must a fast pointer (moving 2) and a slow pointer (moving 1) meet if there is a cycle?
The gap shrinks by one each step. Once both pointers are within the loop, think in the loop's frame: fast advances 2 and slow advances 1, so their separation decreases by 1 every step. A non-negative integer that strictly decreases must hit 0 — the collision — and it cannot “jump over” because the step difference is exactly 1. On a list with no loop, fast escapes to null first, so meeting is a sound proof of a cycle.
A hash-set solution stores every visited node and flags the first repeat. Both are O(n) time — when would you still prefer it?
Floyd wins for pure detection; a set trades space for simplicity. The tortoise-and-hare gives O(1) space and, with a second phase, the loop's start — so it is the interview-expected answer. A visited-set is easier to reason about and generalises when you must attach information to each node or handle concurrent mutation, at the cost of O(n) memory. Knowing precisely what the O(1) method buys (and what it costs in cleverness) is the point of contrasting them.
Floyd's trick: run slow (+1) and fast (+2). On a straight list fast simply runs off the end. If there is a loop, fast enters it first and gains one node on slow each step, so it eventually laps and collides with it — a meeting is impossible without a cycle. O(1) space, unlike a hash set of visited nodes. The curved arrow is the tail's next pointing back into the list.
“Does the list have a cycle” / “is it infinite”. The O(1)-space answer is Floyd's tortoise and hare; the hash-set answer is O(n) space and usually not what is wanted.
Run slow one step and fast two. If fast reaches null there is no loop; if it ever equals slow, a cycle exists — inside a loop the fast pointer closes the one-node gap each step and must collide.
// Two speeds: a meeting can only happen inside a loop. bool hasCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; // +1 fast = fast->next->next; // +2 if (slow == fast) return true; // collision => cycle } return false; // fast reached null => no cycle }
// Two speeds: a meeting can only happen inside a loop. public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; // +1 fast = fast.next.next; // +2 if (slow == fast) return true; // collision => cycle } return false; // fast reached null => no cycle }
# Two speeds: a meeting can only happen inside a loop. def hasCycle(head): slow = fast = head while fast and fast.next: slow = slow.next # +1 fast = fast.next.next # +2 if slow is fast: # collision => cycle return True return False # fast reached null => no cycle
Comparing values instead of nodes, and the null guard. Compare the pointers themselves (slow == fast), not slow->val == fast->val — equal values do not mean the same node. And the loop needs fast && fast->next so the double step never dereferences null on an acyclic list.
The walkthrough for #03 Linked List Cycle. Watch it, then go straight back and write it yourself.
Finding where a cycle begins is the elegant sequel to detecting it. After the tortoise and hare meet, reset one pointer to head, leave the other at the meeting point, and advance both one step at a time. They meet again exactly at the loop's entrance — a consequence of a short distance identity, not a coincidence.
ONCE YOU KNOW A LOOP EXISTS, HOW DO YOU FIND THE NODE WHERE IT STARTS?
In phase 2 (finding the loop's start), how fast do the two pointers move?
Both move one step at a time. Phase 2 is a different walk from phase 1: reset one pointer to head, leave the other where they collided, and single-step them together. The distances work out so that they converge precisely at the loop's entry node. Keeping the fast pointer at double speed here is the classic bug — it overshoots the start. The two phases use the same pointers with different step sizes.
Intuitively, why does resetting one pointer to the head and single-stepping land both at the loop's start?
Two equal distances, so equal-speed walks meet. Let the distance from the head to the loop start be a, and let the tortoise and hare meet at distance b into the loop; the algebra of “fast went twice as far” forces a to equal the remaining loop distance from the meeting point back to the start. So a pointer from head and a pointer from the meeting point, both moving one step, cover the same distance and collide at the entrance. You do not need to reproduce the proof under pressure — you need to remember the two-phase recipe and that phase 2 is single-step.
Detecting the loop is half the job; finding where it begins is the elegant half. After the tortoise and hare meet, reset one pointer to head, leave the other at the meeting point, and advance both one step at a time — they meet again exactly at the loop's entrance. The reason is a short distance argument: the gap from head to the start equals the gap from the meeting point to the start, modulo the loop length.
“Return the node where the cycle begins” (or null). Detection plus a second phase: reset one pointer to the head and single-step both to the loop's entrance.
Phase 1 is Floyd detection — get the tortoise and hare to meet. Phase 2: move one pointer back to head, keep the other at the meeting point, and advance both by one; they meet at the loop's start because the head-to-start distance equals the meet-to-start distance around the loop.
// Detect, then reset one pointer to head and single-step both. ListNode* detectCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { // phase 1: meeting point slow = head; // phase 2: reset one pointer while (slow != fast) { // step BOTH by one slow = slow->next; fast = fast->next; } return slow; // the loop's start } } return nullptr; // no cycle }
// Detect, then reset one pointer to head and single-step both. public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // phase 1: meeting point slow = head; // phase 2: reset one pointer while (slow != fast) { // step BOTH by one slow = slow.next; fast = fast.next; } return slow; // the cycle entry } } return null; // no cycle at all }
# Detect, then reset one pointer to head and single-step both. def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: # phase 1: meeting point slow = head # phase 2: reset one pointer while slow is not fast: # step BOTH by one slow = slow.next fast = fast.next return slow # the loop's start return None # no cycle
Stepping fast by two in phase 2, or forgetting the no-cycle exit. Phase 2 must advance both pointers one node at a time — keeping the hare at double speed overshoots the start. And if fast reaches null, there is no cycle: return null rather than entering phase 2.
The walkthrough for #04 Linked List Cycle II. Watch it, then go straight back and write it yourself.
Checking a linked list for a palindrome in O(1) space is a composition of three fundamentals: find the middle with fast/slow, reverse the second half in place, then walk one pointer from the front and one from the reversed back, comparing values. All pairs match ⇒ palindrome. The clearest proof that mediums are fundamentals stacked together.
HOW DO YOU CHECK A PALINDROME WITHOUT COPYING THE LIST INTO AN ARRAY?
The O(1)-space palindrome check reuses three earlier operations. Name them in order.
Middle → reverse half → compare. Locate the midpoint with fast/slow, reverse the nodes from the middle to the end in place, then run one pointer from the head and one from the new (reversed) second-half head, comparing values until they cross. Every step is a primitive from earlier units; the art is only in sequencing them and handling the odd-length middle node (which can be skipped). This composition mindset is what turns the deck-3 hards from scary into routine.
An easier palindrome solution pushes all values onto a stack (or into a vector) and compares. Why might an interviewer reject it?
Correct, but O(n) space when O(1) is required. Copying the list into a stack or array and mirror-comparing is the obvious approach and a fine first answer — but the standard follow-up is “now do it in O(1) space,” which forces the reverse-the-half technique. Recognising that the space follow-up is really asking “can you compose middle + reverse?” is the signal this unit trains.
The O(1)-space palindrome check chains three primitives you already know. Find the middle with fast/slow, reverse the second half in place, then walk one pointer from the front and one from the reversed half, comparing values. All matches ⇒ palindrome. It is the clearest demonstration that the medium problems are just the fundamentals composed — and politely, you restore the list by reversing the half back.
“Is the list a palindrome”, ideally in O(1) space. The follow-up that forbids an array is really asking you to compose middle + reverse + compare.
Find the middle with fast/slow, reverse the second half in place, then walk one pointer from the head and one from the reversed half comparing values; any mismatch means not a palindrome. Optionally reverse the half back to restore the list.
// Compose three primitives: middle, reverse half, compare ends. bool isPalindrome(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { // 1) find the middle slow = slow->next; fast = fast->next->next; } ListNode *prev = nullptr; // 2) reverse the second half while (slow) { ListNode* next = slow->next; slow->next = prev; prev = slow; slow = next; } ListNode *p = head, *q = prev; // 3) compare from both ends while (q) { if (p->val != q->val) return false; p = p->next; q = q->next; } return true; }
// Compose three primitives: middle, reverse half, compare ends. public boolean isPalindrome(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { // 1) find the middle slow = slow.next; fast = fast.next.next; } ListNode prev = null; // 2) reverse the second half while (slow != null) { ListNode next = slow.next; slow.next = prev; prev = slow; slow = next; } ListNode p = head, q = prev; // 3) compare from both ends while (q != null) { if (p.val != q.val) return false; p = p.next; q = q.next; } return true; }
# Compose three primitives: middle, reverse half, compare ends. def isPalindrome(head): slow = fast = head while fast and fast.next: # 1) find the middle slow, fast = slow.next, fast.next.next prev = None # 2) reverse the second half while slow: nxt = slow.next slow.next, prev, slow = prev, slow, nxt p, q = head, prev # 3) compare from both ends while q: if p.val != q.val: return False p, q = p.next, q.next return True
The O(n)-space stack is a first answer, not the final one. Pushing all values and mirror-comparing is correct but uses O(n) memory; the expected follow-up needs O(1), which forces the reverse-the-half approach. Handle the odd-length middle node (it can be skipped) and, if the list must survive, reverse the half back.
The walkthrough for #05 Palindrome Linked List. Watch it, then go straight back and write it yourself.
You cannot count from the end of a singly list, so manufacture a gap. Advance fast n nodes ahead of slow, then move both together; when fast hits the last node, the preserved gap of n leaves slow exactly one before the target. A dummy head makes removing the first node just another case.
HOW DO YOU REMOVE THE n-th NODE FROM THE END IN A SINGLE PASS?
Why start slow at a dummy node (before the head) rather than at the head itself?
So the head is not a special case. If the node to delete is the very first one (n equals the length), you still need a prev to run prev->next = prev->next->next; the dummy is that predecessor. Anchoring slow at the dummy and advancing fast n + 1 from it leaves slow one before the target in every case, head included. Then return dummy->next as the possibly-new head.
On 1 → 2 → 3 → 4 → 5 with n = 2, which node is removed, and where does slow stop?
Node 4 is removed; slow stops at 3. The 2nd node from the end of 1→2→3→4→5 is 4. Advance fast 2 steps to node 3 (value 3), then move both until fast reaches the last node (5): slow travels 1→2→3 and lands on 3, exactly one before 4. slow->next = slow->next->next bypasses 4, giving 1→2→3→5. The MECHANISM slide opens the gap first, then walks both pointers in lockstep.
You cannot index from the end of a singly list, so manufacture the offset: move fast n nodes ahead, then advance fast and slow together. When fast reaches the last node, the preserved gap of n puts slow exactly one before the target — bypass it. A dummy head handles the case where the node to remove is the head itself, which is the edge case this problem is really testing.
“Remove the n-th node from the end” in one pass. You cannot index from the end of a singly list, so build a fixed-gap two-pointer window behind a dummy head.
Put a dummy before the head. Advance fast n + 1 nodes from the dummy, then move fast and slow together until fast is null; slow now sits just before the target. Bypass it and return dummy->next.
// A gap of n turns 'from the end' into 'from the start'. Dummy handles head. ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next = head; ListNode* fast = &dummy; ListNode* slow = &dummy; for (int i = 0; i <= n; i++) fast = fast->next; // gap of n (+1 from dummy) while (fast) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; // unlink the target return dummy.next; }
// A gap of n turns 'from the end' into 'from the start'. Dummy handles head. public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; for (int i = 0; i <= n; i++) fast = fast.next; // gap of n (+1 from dummy) while (fast != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; // unlink the target return dummy.next; }
# A gap of n turns 'from the end' into 'from the start'. Dummy handles head. def removeNthFromEnd(head, n): dummy = ListNode(0, head) fast = slow = dummy for _ in range(n + 1): # gap of n (+1 from the dummy) fast = fast.next while fast: fast, slow = fast.next, slow.next slow.next = slow.next.next # unlink the target return dummy.next
Off-by-one on the gap, and the head-removal case. Advancing fast exactly n + 1 from the dummy leaves slow one before the target; n steps stops one short. The dummy is not optional: when n equals the length, the node to remove is the head, and only the dummy gives it a predecessor to splice against.
The walkthrough for #06 Remove Nth Node From End of List. Watch it, then go straight back and write it yourself.
Deleting the middle node is finding the middle with one addition: to unlink the node slow lands on, you need the node before it. A singly node cannot reach its own predecessor, so carry prev alongside slow as they walk. At the middle, prev->next = slow->next drops it — the fast/slow engine plus one trailing pointer.
HOW DO YOU DELETE THE MIDDLE WHEN YOU CAN'T LOOK BACKWARD FROM IT?
Why must you track prev to delete the middle, when you already have slow sitting on it?
You delete a node through its predecessor. Removing slow means making the node before it skip over it: prev->next = slow->next. But a singly linked node has no prev field, so if you only kept slow you would have to re-walk from the head to find its predecessor. Carrying prev one hop behind slow during the same fast/slow pass gives it to you for free. (A doubly list, by contrast, could delete in O(1) with no prev variable — that is deck 1's lesson paying off.)
On 1 → 2 → 3 → 4 → 5, which node does delete-middle remove?
Node 3. Fast/slow leaves slow on the middle node (value 3) with prev on node 2. Setting prev->next = slow->next links 2 straight to 4, producing 1 → 2 → 4 → 5. For an even list LeetCode deletes the second of the two middles, which the same guard produces. Watch the MECHANISM slide carry prev a step behind slow and strike the middle when it is reached.
Deleting the middle is finding the middle plus one wrinkle: to unlink the node slow lands on, you need the node before it. A singly node cannot reach its own predecessor, so carry prev alongside slow as they walk. When slow reaches the middle, prev->next = slow->next drops it. Same fast/slow engine as the middle problem, one extra pointer.
“Delete the middle node”. Fast/slow to the midpoint, but you must keep the predecessor to unlink it — a singly node can't look backward.
Walk fast (2) and slow (1) while carrying prev one node behind slow. When slow reaches the middle, prev->next = slow->next drops it. Guard the single-node list (delete to empty) — a dummy head makes this uniform.
// Fast/slow finds the middle; prev trails so you can unlink it. ListNode* deleteMiddle(ListNode* head) { if (!head || !head->next) return nullptr; // 1-node deletes to empty ListNode* slow = head; ListNode* fast = head; ListNode* prev = nullptr; while (fast && fast->next) { fast = fast->next->next; // +2 prev = slow; // remember predecessor slow = slow->next; // +1 } prev->next = slow->next; // unlink the middle return head; }
// Fast/slow finds the middle; prev trails so you can unlink it. public ListNode deleteMiddle(ListNode head) { if (head == null || head.next == null) return null; // 1-node -> empty ListNode slow = head; ListNode fast = head; ListNode prev = null; while (fast != null && fast.next != null) { fast = fast.next.next; // +2 prev = slow; // remember predecessor slow = slow.next; // +1 } prev.next = slow.next; // unlink the middle return head; }
# Fast/slow finds the middle; prev trails so you can unlink it. def deleteMiddle(head): if not head or not head.next: return None # 1-node deletes to empty slow = fast = head prev = None while fast and fast.next: fast = fast.next.next # +2 prev = slow # remember predecessor slow = slow.next # +1 prev.next = slow.next # unlink the middle return head
Forgetting the single-node case, or dropping prev. A one-node list must return null (there is a middle to delete and nothing remains); without the guard you dereference a null prev. And you genuinely need prev — a singly node has no back-pointer, so you cannot unlink slow from slow alone.
The walkthrough for #07 Delete the Middle Node of a Linked List. Watch it, then go straight back and write it yourself.
Group nodes by the parity of their position — 1st, 3rd, 5th, then 2nd, 4th — without moving any data. Keep an odd pointer, an even pointer, and a saved evenHead; each round, odd skips to the next odd node and even to the next even one, splitting the list into two interleaved chains. Finally hook odd->next = evenHead.
HOW DO YOU REGROUP BY POSITION IN O(1) SPACE, KEEPING RELATIVE ORDER?
Why save evenHead at the very start of the odd-even rearrange?
You need the even chain's head to stitch the two groups. The final step joins the tail of the odd chain to the front of the even chain: odd->next = evenHead. But as the weave proceeds, the pointers march forward and the original second node — the head of the even chain — would be lost if you had not stashed it. Saving evenHead before the loop is the small piece of bookkeeping the whole rearrange depends on.
On 1 → 2 → 3 → 4 → 5, what does odd-even list produce?
1 → 3 → 5 → 2 → 4. The odd-position nodes are the 1st, 3rd, 5th (values 1, 3, 5) and the even-position nodes are the 2nd, 4th (values 2, 4); each group keeps its original relative order, and the odd chain is hooked to the even head. Note it is about position, not the values being odd or even — a list of 2 → 4 → 6 → 8 would still split by slot. The MECHANISM slide tints the odd-position nodes as the two chains form, then shows the final reorder.
Group nodes by their position's parity — 1st, 3rd, 5th … then 2nd, 4th … — without moving data. Keep an odd pointer and an even pointer and a saved evenHead; each round, odd hops to the next odd node and even to the next even one, splitting the list into two interleaved chains. Finally odd->next = evenHead stitches them: all odd positions, then all even. O(1) space, order preserved within each group.
“Group nodes at odd indices then even indices” (by position, not value), keeping relative order, in O(1) space. A weave-and-stitch rearrange.
Keep odd and even pointers and save evenHead. Each round, odd jumps to even->next (the next odd node) and even to odd->next (the next even node), splitting the list into two chains. Finally odd->next = evenHead joins them.
// Weave into an odd chain and an even chain, then stitch. ListNode* oddEvenList(ListNode* head) { if (!head || !head->next) return head; ListNode* odd = head; ListNode* even = head->next; ListNode* evenHead = even; // SAVE the even head while (even && even->next) { odd->next = even->next; odd = odd->next; // next odd even->next = odd->next; even = even->next; // next even } odd->next = evenHead; // stitch odd -> even return head; }
// Weave into an odd chain and an even chain, then stitch. public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) return head; ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; // SAVE the even head while (even != null && even.next != null) { odd.next = even.next; odd = odd.next; // next odd even.next = odd.next; even = even.next; // next even } odd.next = evenHead; // stitch odd -> even return head; }
# Weave into an odd chain and an even chain, then stitch. def oddEvenList(head): if not head or not head.next: return head odd, even = head, head.next even_head = even # SAVE the even head while even and even.next: odd.next = even.next; odd = odd.next # next odd even.next = odd.next; even = even.next # next even odd.next = even_head # stitch odd -> even return head
Not saving evenHead, and it's position not value. The final stitch needs the first even node, which is lost once the weave starts — stash it before the loop. And the grouping is by index (1st, 3rd, 5th…), not by whether the stored values are odd or even; misreading that solves a different problem.
The walkthrough for #08 Odd Even Linked List. Watch it, then go straight back and write it yourself.
Two lists of possibly different lengths that share a tail. Walk pA along A and pB along B; when either reaches null, redirect it to the other list's head. After one switch each pointer has travelled |A| + |B| nodes, so the length difference cancels and they land on the first shared node together — or both reach null if the lists never meet.
HOW DO YOU FIND WHERE TWO LISTS MERGE, WITHOUT COUNTING THEIR LENGTHS?
Why does redirecting each pointer to the other list's head make them meet at the intersection?
Both travel the same total distance, so the gap disappears. Say A has length a before the shared tail and B has length b; a pointer that walks A then B covers a + (b + shared), and one that walks B then A covers b + (a + shared) — equal totals. So after each has switched once, they are the same number of steps from the end, and they arrive at the first shared node together. If there is no intersection, both hit null after a + b steps and the loop exits. It is the cleanest two-pointer trick in the deck.
Two lists have nodes with equal values in the middle but are otherwise separate objects. Do they intersect?
No — intersection is about identity, not equality. Two lists intersect only if, from some node onward, they are the same physical nodes — the pointers converge and share a tail. Equal values along the way are irrelevant; comparing values would give false positives. The two-pointer method naturally checks identity because it compares the pointers themselves (pA == pB), which is why it returns the actual shared node. Reading “shared node” as address-identity is the conceptual trap here.
Two lists of different lengths that share a tail. Walk pA along A and pB along B; when either hits null, redirect it to the other list's head. After the switch each pointer has travelled |A| + |B| nodes, so the length gap cancels and they arrive at the first shared node together — or both reach null if the lists never meet. No length counting, O(1) space, and the neatest use of the two-pointer idea in the deck.
“Find the node where two lists intersect” (share a tail). The O(1)-space trick is two pointers that switch heads to cancel the length difference.
Walk pA along A and pB along B; when a pointer hits null, redirect it to the other list's head. After one switch each has travelled |A| + |B| nodes, so they align and meet at the first shared node — or both become null together if the lists never intersect.
// Switch heads at each end: both walk |A|+|B|, so lengths cancel. ListNode* getIntersectionNode(ListNode* a, ListNode* b) { ListNode* pA = a; ListNode* pB = b; while (pA != pB) { pA = pA ? pA->next : b; // A exhausted -> head of B pB = pB ? pB->next : a; // B exhausted -> head of A } return pA; // shared node, or null if none }
// Switch heads at each end: both walk |A|+|B|, so lengths cancel. public ListNode getIntersectionNode(ListNode a, ListNode b) { ListNode pA = a; ListNode pB = b; while (pA != pB) { pA = (pA != null) ? pA.next : b; // A exhausted -> head of B pB = (pB != null) ? pB.next : a; // B exhausted -> head of A } return pA; // shared node, or null if none }
# Switch heads at each end: both walk |A|+|B|, so lengths cancel. def getIntersectionNode(a, b): pA, pB = a, b while pA is not pB: pA = pA.next if pA else b # A exhausted -> head of B pB = pB.next if pB else a # B exhausted -> head of A return pA # shared node, or None
Comparing values, and the no-intersection exit. Intersection means the same node (identity), so compare pointers, not ->val. The loop is guaranteed to end: if the lists never meet, both pointers reach null after |A| + |B| steps and pA == pB == null, which correctly returns null — no infinite loop.
The walkthrough for #09 Intersection of Two Linked Lists. Watch it, then go straight back and write it yourself.
The digits are stored reversed, which is the gift: the ones place sits at each head, so you add node by node from the front exactly as you would on paper. Carry a carry, append sum % 10 to a dummy-headed result list, and continue while either input remains or a carry is left over. Return dummy.next.
HOW DO YOU ADD TWO NUMBERS STORED AS LINKED DIGITS, LEAST-SIGNIFICANT FIRST?
Why is the loop condition while (l1 || l2 || carry) instead of while (l1 && l2)?
Unequal lengths and a leftover carry. Stopping when the shorter list ends (&&) truncates the sum; and even after both lists are exhausted, a carry of 1 (as in 99 + 1 = 100) still needs a final node. Looping while any of l1, l2, or carry is non-zero — and treating a missing node as contributing 0 — handles both. It is the most common correctness bug in this problem.
Adding 2 → 4 → 3 and 5 → 6 → 4 (i.e. 342 + 465), what is the result list?
7 → 0 → 8. Add head to head with carry: ones 2+5 = 7 (carry 0); tens 4+6 = 10 → digit 0, carry 1; hundreds 3+4+1 = 8 (carry 0). The result list, still least-significant-first, is 7 → 0 → 8, i.e. the number 807 = 342 + 465. No trailing carry here, but flip one input to make it 999 and you would get the extra node. The MECHANISM slide shows the running carry and the result list growing behind the dummy.
The digits are stored reversed, which is the gift: the ones place is at each head, so you add node by node, front to back, exactly as you would on paper. Carry a carry, append sum % 10 to a dummy-headed result list, and keep going while either input remains or a carry is left over — that final carry (think 99 + 1) is the case people forget. The dummy makes appending uniform from the very first digit.
“Add two numbers given as linked lists, one digit per node, least-significant digit first”. Reversed storage lets you add front to back with a carry, building the result behind a dummy.
Walk both lists together. At each step sum = l1 + l2 + carry; append sum % 10 to a dummy-headed result and set carry = sum / 10. Continue while either list has nodes or a carry remains, treating a missing node as 0.
// Digits are reversed, so add head-to-head with a carry, behind a dummy. ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; int carry = 0; while (l1 || l2 || carry) { int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry; carry = sum / 10; cur->next = new ListNode(sum % 10); // append the digit cur = cur->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } return dummy.next; }
// Digits are reversed, so add head-to-head with a carry, behind a dummy. public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry; carry = sum / 10; cur.next = new ListNode(sum % 10); // append the digit cur = cur.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } return dummy.next; }
# Digits are reversed, so add head-to-head with a carry, behind a dummy. def addTwoNumbers(l1, l2): dummy = ListNode(0) cur = dummy carry = 0 while l1 or l2 or carry: s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry carry = s // 10 cur.next = ListNode(s % 10) # append the digit cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next
Dropping the final carry, or stopping at the shorter list. Loop while l1 || l2 || carry and treat a missing node as 0: ending when the shorter list runs out truncates the sum, and a leftover carry (99 + 1 = 100) needs its own final node. The dummy head makes appending the first digit uniform.
The walkthrough for #10 Add Two Numbers. Watch it, then go straight back and write it yourself.
Palindrome-linked-list in O(1) space is built entirely from three earlier primitives. Which three?
Middle, reverse, compare. There is no new idea in the O(1) palindrome check — it is fast/slow to locate the midpoint, an in-place reversal of the back half, and a two-pointer comparison walking inward from both ends. Recognising a medium problem as a composition of fundamentals is the entire game of this deck: once the three primitives are automatic, the “hard” version is just deciding the order to run them in (and, politely, reversing the half back to leave the list intact).
Remove-nth-from-end and add-two-numbers both open with ListNode dummy; dummy.next = head;. What problem does the dummy head solve in each?
It removes the “the head might change” special case. In remove-nth, the target can be the head itself, so without a dummy you would branch to reassign head; the dummy gives position 0 a real predecessor. In add-two, the dummy is the anchor you append the first result digit to, so building the list is uniform from the start and you simply return dummy.next. Any time an operation can touch the first node, reach for the dummy — it is the single most reused trick across decks 1–3.
Pointer bugs compile and pass the sample: a missing null guard, a flip before the save, a phase-2 step size, a dropped carry. Every one returns a believable wrong answer.
The loop must be while (fast && fast->next) — drop either check and the double step dereferences null on an even-length list. And that exact guard decides whether slow lands on the first or second middle; problems like delete-middle care which.
Save next before flipping curr->next, or the rest of the list is unreachable. And return prev — it walked to the old tail, the new head; returning the old head gives you a one-node list.
Start both at head and advance inside the loop (slow = slow->next; fast = fast->next->next then compare). Starting fast at head->next is a different convention that changes the meeting math — pick one and keep it consistent.
After the meeting, both pointers move one step at a time — not two. Reset one to head, keep the other at the meeting point, and single-step both. Moving fast by two in phase 2 overshoots the loop's start.
The gap must leave slow before the target, so advance fast the right number of steps (with a dummy, n + 1 from the dummy). Removing the head itself (n == length) is why the dummy head is not optional here.
Loop while (l1 || l2 || carry), treating a missing node as 0. Forgetting the trailing carry drops the leading 1 on cases like 99 + 1; stopping when the shorter list ends truncates the answer.
Ten problems, ten one-liners. The right-hand column is the move — the pointer choreography that should come to mind the instant you read the statement.
Fast/slow, reverse, Floyd, the gap, the rearrange, the tandem walk — that is the whole vocabulary. The hards in deck 3 (reverse-in-k-group, sort, LRU, merge-k, copy-random) are these six composed, so once they are automatic the last deck is bookkeeping.
Lectures are Striver's A2Z linked-list playlist (L5, L6, L8–L10, L12–L14, L16, L17). Problems are LeetCode; the hard problems are deck 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.