Coding Drills · 05

Linked Lists Pointer Surgery

Eleven drills on the data structure that punishes sloppy pointer handling. Every problem here reduces to four moves — a dummy head, fast & slow runners, in-place reversal, and gap pointers — applied with discipline about which link you overwrite and when. Each drill has a traced diagram, a complete Java program and the bugs interviewers watch for.

11
Drills
5
Easy
6
Medium
0
Hard
Hub · 01 Arrays & Hashing · 02 Two Pointers · 03 Strings & Sliding Window · 04 Binary Search & Intervals · 05 Linked Lists · 06 Binary Trees & BST · 07 Grids & Matrices · 08 Graphs · 09 Dynamic Programming · 10 Backtracking & Design
01
Chapter One · Core Idea

What a Linked List Really Is

head 7 3 9 null val next no index — only the next reference

A singly linked list is a chain of nodes where each node stores a value and a single reference, next, to the node after it. The list itself is nothing more than a reference to the first node (head); the last node points to null. There is no index and no length field: to reach the k-th node you must walk k links from the head, which makes random access O(n). In exchange, inserting or deleting a node once you hold the node before it is O(1) — you only rewrite one or two references, nothing is shifted.

That trade-off defines every interview problem in this chapter. You are almost never asked to search; you are asked to rewire: reverse links, splice two lists, cut a list in two, skip a node. The difficulty is not the algorithm — it is keeping track of which references are still reachable while you overwrite them. Lose the only pointer to the rest of the list and the nodes are gone (garbage-collected in Java, leaked in C). The four tools in Chapter 03 exist to make that bookkeeping mechanical.

OperationArray / ArrayListSingly linked listWhy
Access k-th elementO(1)O(k)must follow k next links
Insert / delete at headO(n)O(1)array shifts every element; list rewrites head
Insert / delete after a known nodeO(n)O(1)one or two reference writes
Find lengthO(1)O(n)no size field on a bare ListNode
Extra memory per element01 referencethe next pointer
The node class used in every drill
static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } }
Analogy: A linked list is a scavenger hunt. Each clue (node) tells you its prize (val) and where the next clue is hidden (next). You cannot jump to clue 7 — you must follow clues 1 through 6. But if you want to insert a detour, you only rewrite one clue to point at the new one, and the new one to point where the old one used to. Rewrite a clue before copying where it pointed, and the rest of the hunt is lost forever.
02
Chapter Two · Mental Model

How to Think About Pointer Problems

A node only knows its successor, never its predecessor
▶
To delete or insert at position k you must stop at node k-1. Most bugs are off-by-one stops — the "previous node" problem.
The head node has no predecessor
▶
Operations on the head need special-case code — unless you add a dummy node in front, which gives every real node a predecessor.
Overwriting curr.next destroys the only path to the rest of the list
▶
Always save next = curr.next before you rewrite it. Reversal, swapping and partitioning all start with this line.
There is no length and no index
▶
Questions about "the middle", "the n-th from the end" or "is there a loop" are answered with two pointers moving at different speeds or offsets.
Two pointers walking the same list keep a fixed relationship
▶
Speed 2 vs 1 → when fast finishes, slow is halfway. Gap of n → when the leader hits null, the follower is n from the end. Same speed, swapped lists → equal total distance.
Every rewiring is O(1) and nodes are reused
▶
Most drills run in O(n) time and O(1) extra space — creating new nodes is only required when the output is new data (Add Two Numbers).
Which linked-list tool applies?
Does the head itself change (delete/insert/merge)? yes Dummy node in front of head no Need the middle, a cycle, or a meeting point? yes Fast & slow runners (2x vs 1x) no Need "n-th from the end" in one pass? yes Gap pointers (leader n+1 ahead) no Must links point the other way? yes In-place reversal (prev/curr/next) no Building one or two output chains? yes Dummy head + tail pointer per chain Patterns stack: Remove Nth uses dummy + gap; Rotate uses length + ring + cut; Partition uses two dummy chains.
03
Chapter Three · Pattern Toolkit

Four Templates That Solve Everything

Four templates cover all eleven drills. Learn them as muscle memory — in an interview you should be able to write each one without thinking, and spend your attention on the problem-specific twist.

Template A — Dummy head + tail builder
Use when the output list is assembled node by node, or when the real head might be removed.
Pseudocode
function build(source): dummy = new Node(0) // sentinel, never returned tail = dummy for each node chosen from source: tail.next = node // append tail = node // advance tail.next = null // terminate (avoid stale links) return dummy.next
Template A — dummy head grows a list with a tail pointer
start D tail null append 1 D 1 tail null append 1, 2 D 1 2 tail null return dummy.next = [1, 2] — the sentinel absorbs the "empty list" and "new head" special cases
Template B — Fast & slow runners
Use for the middle node, cycle detection, or splitting a list in half.
Pseudocode
function runners(head): slow = head, fast = head while fast != null and fast.next != null: slow = slow.next // 1 step fast = fast.next.next // 2 steps // (cycle check: if slow == fast, there is a loop) return slow // middle (second middle when even)
Template B — slow moves 1, fast moves 2 on [1,2,3,4,5]
iteration 0 1 S F 2 3 4 5 null iteration 1 1 2 S 3 F 4 5 null iteration 2 1 2 3 S 4 5 F null fast.next == null → stop. slow covered half the distance of fast → slow is the middle (3).
Template C — In-place reversal
Use whenever links must point backwards: full reversal, reversing a sub-range, palindrome check on the second half.
Pseudocode
function reverse(head): prev = null, curr = head while curr != null: next = curr.next // save curr.next = prev // flip prev = curr // advance curr = next return prev
Template C — three pointers flip one link per iteration
before A curr B C null prev = null after 1 flip A prev B curr C null null after 2 flips A B prev C curr null null save → flip → advance. The saved "next" is the only bridge to the unreversed part.
Template D — Gap pointers / length-then-walk
Use when a position is defined relative to the end ("n-th from the end", "rotate by k").
Pseudocode
function nodeBeforeNthFromEnd(head, n): dummy.next = head lead = dummy, follow = dummy repeat n + 1 times: lead = lead.next // open the gap while lead != null: // slide together lead = lead.next follow = follow.next return follow // follow.next is the target
Template D — fixed gap between two pointers
gap opened n = 2, lead +3 D follow 1 2 3 lead 4 5 null slid to end D 1 2 3 follow 4 target 5 null lead = null The gap of n + 1 links never changes, so when lead falls off the end, follow is exactly one node before the target.
Universal checklist before you write any pointer code:
  • Draw three nodes on paper and write the reference assignments in order — the order is the algorithm.
  • Ask: does the head change? If yes, add a dummy node.
  • Ask: what is the loop condition for an empty list, one node, and two nodes? Test all three mentally.
  • Compare nodes with == (identity) when the question is "same node", never by val.
04
Drill 40 · Reversal

Reverse Linked List

Drill 40 — Reverse Linked List
Easyin-place reversalLeetCode 206 ↗
Given the head of a singly linked list, reverse the list and return the new head.
Example
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Input: head = [] Output: []
Key insight: You do not move nodes — you flip arrows. Walk the list once and make each node point to the one behind it. The only danger is that flipping curr.next erases your route forward, so save it first. Three references (prev, curr, next) are all you ever need.
From brute force to optimal

The brute-force approach copies values into an array (or a stack) and writes them back in reverse — O(n) time but O(n) extra space, and it changes values rather than structure, which interviewers usually reject. The optimal approach rewires each link in place in a single pass: O(n) time, O(1) space. A recursive version is elegant (head.next.next = head) but uses O(n) stack and overflows on lists of ~104+ nodes with default JVM settings.

Walkthrough
Reversing [1,2,3,4,5] — green nodes are already reversed
start 1 curr 2 3 4 5 null after 1 iter 1 prev 2 curr 3 4 5 null null after 2 iter 1 2 prev 3 curr 4 5 null null after 5 iter 1 2 3 4 5 prev null prev = null curr = null → return prev (5)
Iternext savedcurr.next = prevprevcurrReversed part
121 → null121
232 → 1232 → 1
343 → 2343 → 2 → 1
454 → 3454 → 3 → 2 → 1
5null5 → 45null5 → 4 → 3 → 2 → 1
Java — complete solution with main()
public class ReverseLinkedList { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Iterative three-pointer reversal: O(n) time, O(1) space static ListNode reverseList(ListNode head) { ListNode prev = null, curr = head; while (curr != null) { ListNode next = curr.next; // 1. save the rest of the list curr.next = prev; // 2. flip this node's link prev = curr; // 3. prev steps forward curr = next; // 4. curr steps forward } return prev; // prev is the old tail = new head } // Recursive variant: O(n) time, O(n) call stack static ListNode reverseRecursive(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseRecursive(head.next); head.next.next = head; // the node after me now points back to me head.next = null; // I become the tail (for now) return newHead; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(reverseList(build(1, 2, 3, 4, 5)))); // [5,4,3,2,1] System.out.println(str(reverseRecursive(build(1, 2)))); // [2,1] System.out.println(str(reverseList(null))); // [] } }
ApproachTimeSpaceNotes
Copy to array / stackO(n)O(n)rewrites values, not links
Iterative three-pointerO(n)O(1)interview answer
RecursiveO(n)O(n) stackrisk of StackOverflowError on long lists
⚠ Common bugs & edge cases:
  • Forgetting to save curr.next before overwriting it — the rest of the list becomes unreachable.
  • Returning head instead of prev: after the loop the old head is the tail.
  • Recursive version: forgetting head.next = null creates a 2-node cycle between the first two nodes.
  • Empty list and single node must work without special cases — the loop simply runs 0 or 1 times.
05
Drill 41 · Merge

Merge Two Sorted Lists

Drill 41 — Merge Two Sorted Lists
Easydummy + tailLeetCode 21 ↗
Given the heads of two sorted linked lists l1 and l2, splice their nodes into one sorted list and return its head.
Example
Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4] Input: l1 = [], l2 = [0] Output: [0]
Key insight: This is the merge step of merge sort. Two "fronts" compete; the smaller one is moved onto the output and its list advances. A dummy head means you never have to ask "is this the first node?", and when one list empties the other is already sorted, so you attach it whole.
From brute force to optimal

Brute force: collect all values into an array, sort, rebuild — O((n+m) log(n+m)) time and O(n+m) space, and it ignores that the inputs are already sorted. The optimal merge compares only the two fronts, so each node is touched once: O(n+m) time. Because we relink existing nodes instead of allocating new ones, extra space is O(1). A recursive merge is shorter but costs O(n+m) stack.

Walkthrough
Merging [1,2,4] and [1,3,4] — colour shows which list each node came from
l1 1 2 4 null l2 1 3 4 null merged D 1 l1 1 l2 2 l1 3 l2 4 l1 4 splice null Tie 1 vs 1 → take l1 first (<= keeps it stable). When l1 runs out, the rest of l2 (4) is attached in one assignment.
Stepl1l2CompareAppendMerged so far
1111 <= 1l1:11
2212 > 1l2:11,1
3232 <= 3l1:21,1,2
4434 > 3l2:31,1,2,3
5444 <= 4l1:41,1,2,3,4
6null4loop endssplice l21,1,2,3,4,4
Java — complete solution with main()
public class MergeTwoSortedLists { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Dummy head + tail pointer: O(n + m) time, O(1) extra space static ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { // <= keeps the merge stable tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = (l1 != null) ? l1 : l2; // splice the leftover run in O(1) return dummy.next; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(mergeTwoLists(build(1, 2, 4), build(1, 3, 4)))); // [1,1,2,3,4,4] System.out.println(str(mergeTwoLists(null, build(0)))); // [0] System.out.println(str(mergeTwoLists(null, null))); // [] } }
ApproachTimeSpaceNotes
Collect, sort, rebuildO((n+m) log(n+m))O(n+m)ignores sortedness
Iterative mergeO(n+m)O(1)relinks existing nodes
Recursive mergeO(n+m)O(n+m) stackconcise but deep recursion
⚠ Common bugs & edge cases:
  • Forgetting tail = tail.next after appending — every node overwrites the same slot.
  • Looping until both lists are null and dereferencing the null one; stop when either is null and splice the remainder.
  • Returning dummy instead of dummy.next adds a phantom 0 at the front.
  • Using < instead of <= still sorts correctly but is not stable — matters when nodes carry satellite data.
06
Drills 42–43 · Fast & Slow

Cycle Detection & Middle Node

Drill 42 — Linked List Cycle
Easyfast & slowLeetCode 141 ↗
Given head, return true if some node can be reached again by continuously following next (the list contains a cycle), otherwise false. pos in the examples only describes the input; it is not passed to your function.
Example
Input: head = [3,2,0,-4], pos = 1 Output: true // tail connects back to the node at index 1 Input: head = [1], pos = -1 Output: false
Key insight: Two runners on a circular track: if the track is a loop, the faster runner must eventually lap the slower one. Inside the cycle the gap between them shrinks by exactly one node per iteration, so fast cannot "jump over" slow — they meet within one lap. If there is no loop, fast simply reaches null.
From brute force to optimal

The obvious solution stores every visited node in a HashSet<ListNode> and reports a cycle on the first repeat — O(n) time but O(n) space. Floyd's algorithm replaces the set with a second pointer moving at double speed: O(n) time (slow enters the cycle within n steps and is caught within one more lap) and O(1) space.

Walkthrough
Floyd on [3,2,0,-4] with tail → index 1: the runners meet at -4
3 idx 0 2 idx 1 0 idx 2 -4 idx 3 tail.next = node at idx 1 (pos = 1) list start slow → idx 0 (3) fast → idx 0 (3) iter 1 slow → idx 1 (2) fast → idx 2 (0) iter 2 slow → idx 2 (0) fast → idx 1 (2) fast wrapped: 3 → 1 iter 3 slow → idx 3 (-4) fast → idx 3 (-4) slow == fast → true
Java — complete solution with main()
public class LinkedListCycle { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Floyd's tortoise and hare: O(n) time, O(1) space static boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps if (slow == fast) return true; // compare references, not values } return false; // fast fell off the end: no cycle } // Builds a list and links the tail to index pos (-1 = no cycle) static ListNode build(int pos, int... vals) { ListNode dummy = new ListNode(0), tail = dummy, entry = null; for (int i = 0; i < vals.length; i++) { tail.next = new ListNode(vals[i]); tail = tail.next; if (i == pos) entry = tail; } tail.next = entry; return dummy.next; } public static void main(String[] args) { System.out.println(hasCycle(build(1, 3, 2, 0, -4))); // true (tail -> node 2) System.out.println(hasCycle(build(0, 1, 2))); // true (tail -> head) System.out.println(hasCycle(build(-1, 1))); // false } }
ApproachTimeSpaceNotes
HashSet of visited nodesO(n)O(n)simple, extra memory
Floyd tortoise & hareO(n)O(1)interview answer
⚠ Common bugs & edge cases:
  • Checking slow == fast before moving — both start at head, so it returns true immediately.
  • Loop guard must be fast != null && fast.next != null, in that order, or fast.next.next throws NPE.
  • Comparing slow.val == fast.val — duplicate values give false positives; compare references.
  • Follow-up (LC 142): to find the cycle entry, reset one pointer to head after the meeting and advance both by 1; they meet at the entry.
Drill 43 — Middle of the Linked List
Easyfast & slowLeetCode 876 ↗
Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one.
Example
Input: head = [1,2,3,4,5] Output: node 3 (list from there: [3,4,5]) Input: head = [1,2,3,4,5,6] Output: node 4 (list from there: [4,5,6])
Key insight: If one runner moves twice as fast as the other, the slow runner is always at half the distance. When fast can no longer take a full double step, slow is in the middle — no length needed. The loop guard decides which middle you land on for even lengths.
From brute force to optimal

The two-pass approach counts the length n, then walks n/2 steps — O(n) time, O(1) space, perfectly acceptable but two traversals. The runner technique does it in one pass with the same complexity. The real value is that it composes: palindrome check, reorder list and merge sort on lists all start with "find the middle".

Walkthrough
Odd length stops on the middle; even length stops on the second middle
start 1 slow fast 2 3 4 5 null iter 1 1 2 slow 3 fast 4 5 null iter 2 1 2 3 slow 4 5 fast null fast.next == null even: start 1 slow fast 2 3 4 5 6 null iter 1 1 2 slow 3 fast 4 5 6 null iter 2 1 2 3 slow 4 5 fast 6 null iter 3 1 2 3 4 slow 5 6 null fast = null → slow = 4
Java — complete solution with main()
public class MiddleOfLinkedList { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Fast moves 2, slow moves 1: when fast ends, slow is in the middle. // Even length returns the SECOND middle. O(n) time, O(1) space. static ListNode middleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } public static void main(String[] args) { System.out.println(middleNode(build(1, 2, 3, 4, 5)).val); // 3 System.out.println(middleNode(build(1, 2, 3, 4, 5, 6)).val); // 4 (second middle) System.out.println(middleNode(build(7)).val); // 7 } }
ApproachTimeSpaceNotes
Count length, then walk n/2O(n)O(1)two passes
Fast & slowO(n)O(1)one pass
Copy into ArrayListO(n)O(n)unnecessary memory
⚠ Common bugs & edge cases:
  • Want the first middle for even lengths (needed to split a list for merge sort)? Use while (fast.next != null && fast.next.next != null).
  • Starting fast at head.next silently switches which middle you get — be deliberate.
  • A single node is its own middle; an empty list returns null — both handled by the loop guard.
07
Drill 44 · Gap Pointers

Remove Nth Node From End

Drill 44 — Remove Nth Node From End of List
Mediumdummy + gap pointersLeetCode 19 ↗
Given the head of a linked list, remove the n-th node from the end and return the head. 1 <= n <= length.
Example
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Input: head = [1], n = 1 Output: [] Input: head = [1,2], n = 2 Output: [2]
Key insight: "n-th from the end" is a fixed distance from null. Put two pointers n+1 links apart and slide them together: when the leader falls off the end, the follower is parked on the node before the one to delete — exactly where you need to be to unlink it. Starting both at a dummy node makes deleting the real head an ordinary case.
From brute force to optimal

Two-pass: count the length L, then walk L-n steps and unlink — O(L) time, O(1) space, but two traversals and an extra head special case. The one-pass gap technique keeps the same bounds while touching each node at most twice. Interviewers often add "in one pass" specifically to push you toward the gap pointers.

Walkthrough
Removing the 2nd node from the end of [1,2,3,4,5]
gap open fast moved n+1 = 3 D slow 1 2 3 fast 4 5 null slide x3 fast = null D 1 2 3 slow 4 target 5 null unlink slow.next = slow.next.next D 1 2 3 slow 5 null Return dummy.next → [1,2,3,5]. If n equals the length, slow stays on D and the real head is removed — no special case.
PhasefastslowNote
open gap (3 moves)D→1→2→3Dgap = n + 1 links
slide 141
slide 252
slide 3null3stop
unlink—33.next = 5 (node 4 removed)
Java — complete solution with main()
public class RemoveNthFromEnd { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // One pass with an n-node gap: O(L) time, O(1) space static ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; // dummy makes "remove the head" a normal case ListNode fast = dummy, slow = dummy; for (int i = 0; i <= n; i++) { // open a gap of n + 1 links fast = fast.next; } while (fast != null) { // slide the window to the end fast = fast.next; slow = slow.next; } slow.next = slow.next.next; // slow sits just BEFORE the target return dummy.next; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(removeNthFromEnd(build(1, 2, 3, 4, 5), 2))); // [1,2,3,5] System.out.println(str(removeNthFromEnd(build(1), 1))); // [] System.out.println(str(removeNthFromEnd(build(1, 2), 2))); // [2] } }
ApproachTimeSpaceNotes
Two passes (length, then walk)O(L)O(1)needs head special case without dummy
Dummy + gap, one passO(L)O(1)interview answer
Store nodes in a listO(L)O(L)index L-n-1 directly
⚠ Common bugs & edge cases:
  • Gap of n instead of n+1 leaves slow on the target, and you cannot unlink a node from itself in a singly linked list.
  • Without a dummy, removing the head (n == length) needs a separate branch — and is the most frequently failed test case.
  • Moving fast n+1 times from head (not dummy) throws NPE when n == length.
08
Drill 45 · Simulation

Add Two Numbers

Drill 45 — Add Two Numbers
Mediumsimulation + dummyLeetCode 2 ↗
Two non-empty linked lists represent two non-negative integers with digits stored in reverse order (one digit per node). Add the numbers and return the sum as a linked list in the same format. No leading zeros except the number 0 itself.
Example
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] // 342 + 465 = 807 Input: l1 = [9,9,9], l2 = [1] Output: [0,0,0,1] // 999 + 1 = 1000: the final carry creates a new node
Key insight: Reverse order is a gift: the head is the ones digit, so you add column by column exactly as on paper, moving left-to-right through the lists. Treat a finished list as an endless supply of zeros, and keep looping while either list or the carry is non-zero.
From brute force to optimal

Converting each list to an int/long, adding, and converting back fails as soon as the numbers exceed 19 digits (lists can have 100 nodes). BigInteger works but sidesteps the exercise. Digit-by-digit addition with a carry is O(max(n, m)) time; the output list has max(n, m) + 1 nodes at most, and apart from it only O(1) extra space is used.

Walkthrough
342 + 465 = 807, one digit per node, carry flows right
carry in l1 l2 result carry out 0 2 5 2+5+0=7 7 0 0 4 6 4+6+0=10 0 1 1 3 4 3+4+1=8 8 0 → null ← carry out of column 2 = 342 = 465 = 807 Digits are stored least-significant first, so the lists are already in the order grade-school addition processes them.
Java — complete solution with main()
public class AddTwoNumbers { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Grade-school addition, least significant digit first. // O(max(n, m)) time, O(1) extra space besides the output list. static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), tail = dummy; int carry = 0; while (l1 != null || l2 != null || carry != 0) { int sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; tail.next = new ListNode(sum % 10); tail = tail.next; } return dummy.next; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(addTwoNumbers(build(2, 4, 3), build(5, 6, 4)))); // [7,0,8] 342 + 465 = 807 System.out.println(str(addTwoNumbers(build(9, 9, 9), build(1)))); // [0,0,0,1] 999 + 1 = 1000 System.out.println(str(addTwoNumbers(build(0), build(0)))); // [0] } }
ApproachTimeSpaceNotes
Convert to long, add, convert backO(n+m)O(1)overflows beyond 19 digits — wrong
BigIntegerO(n+m)O(n+m)correct, but avoids the point
Digit simulation with carryO(max(n,m))O(1) extraoutput list not counted
⚠ Common bugs & edge cases:
  • Stopping when both lists end and forgetting the last carry: 5 + 5 must return [0,1], not [0].
  • Advancing l1 = l1.next when l1 is already null — guard each list separately.
  • Variant (LC 445) stores digits most-significant first: reverse both lists first, or use two stacks.
09
Drill 46 · Rewiring

Swap Nodes in Pairs

Drill 46 — Swap Nodes in Pairs
Mediumdummy + rewiringLeetCode 24 ↗
Given a linked list, swap every two adjacent nodes and return its head. You must change the links, not the values. A trailing odd node stays in place.
Example
Input: head = [1,2,3,4] Output: [2,1,4,3] Input: head = [1,2,3] Output: [2,1,3] Input: head = [] Output: []
Key insight: Each swap touches three links: the one coming into the pair, the one between the pair, and the one leaving it. Keep an anchor prev on the node just before the pair; a dummy gives the first pair an anchor too. After the swap, the old first is the pair's tail and becomes the next anchor.
From brute force to optimal

Swapping val fields is trivial but explicitly forbidden. The recursive solution (second.next = swapPairs(second.next)) is short but uses O(n) stack. The iterative rewire visits each node once with four assignments per pair: O(n) time, O(1) space.

Walkthrough
Swapping pairs in [1,2,3,4]: the prev anchor walks two nodes per round
start D prev 1 first 2 second 3 4 null round 1 done D 2 1 prev 3 first 4 second null round 2 done D 2 1 4 3 prev null prev.next == null → stop Inside one round: (1) first.next = second.next (2) second.next = first (3) prev.next = second (4) prev = first Step 1 must happen before step 2 — otherwise the link to node 3 is lost.
Java — complete solution with main()
public class SwapNodesInPairs { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Rewire pairs behind a "prev" anchor: O(n) time, O(1) space static ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode first = prev.next; ListNode second = first.next; first.next = second.next; // 1. first skips over second second.next = first; // 2. second points back to first prev.next = second; // 3. anchor now points at second prev = first; // 4. first is the tail of this pair } return dummy.next; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(swapPairs(build(1, 2, 3, 4)))); // [2,1,4,3] System.out.println(str(swapPairs(build(1, 2, 3)))); // [2,1,3] System.out.println(str(swapPairs(build()))); // [] } }
ApproachTimeSpaceNotes
Swap valuesO(n)O(1)not allowed by the problem
RecursiveO(n)O(n) stackelegant, deep recursion
Iterative with dummyO(n)O(1)interview answer
⚠ Common bugs & edge cases:
  • Wrong assignment order loses node 3 — write the four lines on paper with three boxes first.
  • Advancing prev = second instead of prev = first: after the swap, first is the later node.
  • Guard must check both prev.next and prev.next.next to leave an odd tail untouched.
  • Generalisation (LC 25, Reverse Nodes in k-Group) uses the same anchor idea with Template C on each block.
10
Drill 47 · Ring & Cut

Rotate List

Drill 47 — Rotate List
Mediumlength + ring + cutLeetCode 61 ↗
Given the head of a linked list, rotate the list to the right by k places. k can be much larger than the length (up to 2·109).
Example
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3] Input: head = [0,1,2], k = 4 Output: [2,0,1] // 4 % 3 = 1 effective rotation
Key insight: A rotation does not move nodes — it just changes where the list "starts". Join the tail to the head to make a ring, then cut the ring at the right place. The new tail is length - k - 1 steps from the old head (after reducing k %= length).
From brute force to optimal

Rotating one step at a time (move the tail to the front, k times) costs O(n·k) — hopeless for k = 2·109. Measuring the length first lets you reduce k modulo n and locate the cut directly: one pass to measure, at most one more to the cut, O(n) time and O(1) space.

Walkthrough
Rotate [1,2,3,4,5] right by k = 2 → [4,5,1,2,3]
measure length = 5, k = 2 % 5 = 2 1 2 3 4 5 tail null close ring walk 5-2-1 = 2 steps 1 2 3 newTail 4 newHead 5 tail.next = head cut result 4 head 5 1 2 3 null Rotating right by k = moving the last k nodes to the front. Only two links change: tail → head, and newTail → null.
Java — complete solution with main()
public class RotateList { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Measure, close into a ring, cut at the new tail: O(n) time, O(1) space static ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; int length = 1; ListNode tail = head; while (tail.next != null) { // find the tail and the length tail = tail.next; length++; } k %= length; // k may be far larger than length if (k == 0) return head; tail.next = head; // close the ring ListNode newTail = head; for (int i = 0; i < length - k - 1; i++) { newTail = newTail.next; // walk to node (length - k - 1) } ListNode newHead = newTail.next; newTail.next = null; // cut the ring return newHead; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(rotateRight(build(1, 2, 3, 4, 5), 2))); // [4,5,1,2,3] System.out.println(str(rotateRight(build(0, 1, 2), 4))); // [2,0,1] (4 % 3 = 1) System.out.println(str(rotateRight(build(1, 2), 2))); // [1,2] (full turn) } }
ApproachTimeSpaceNotes
Move tail to front k timesO(n·k)O(1)time-limit exceeded
Measure, ring, cutO(n)O(1)k reduced mod n
⚠ Common bugs & edge cases:
  • Not reducing k %= length — walks billions of steps around the ring.
  • When k % length == 0, return immediately; otherwise you close the ring and cut it in the same place, which works, but forgetting to cut creates a cycle.
  • Off-by-one on the walk: the new tail is reached after length - k - 1 steps from head, the new head is the node after it.
  • Empty list: computing k % 0 throws ArithmeticException — guard head == null first.
11
Drill 48 · Split & Weave

Odd Even Linked List

Drill 48 — Odd Even Linked List
Mediumsplit & weaveLeetCode 328 ↗
Group all nodes at odd positions (1st, 3rd, …) followed by all nodes at even positions, preserving relative order within each group. O(1) extra space, O(n) time.
Example
Input: head = [1,2,3,4,5] Output: [1,3,5,2,4] Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]
Key insight: Two interleaved chains are already inside the list — odd and even nodes alternate. Let each chain "jump over" one node of the other. Remember where the even chain started (evenHead), because at the end the odd chain's tail must point to it.
From brute force to optimal

Copying odd-position values, then even-position values, into a new list uses O(n) space and violates the constraint. The weave rewires in place: every iteration advances both chains by one node, so the loop runs about n/2 times — O(n) time, O(1) space.

Walkthrough
Odd Even Linked List on [1,2,3,4,5]: weave two chains, then glue
input 1 pos 1 2 pos 2 3 pos 3 4 pos 4 5 pos 5 null odd chain 1 3 5 even chain 2 evenHead 4 even null odd.next = evenHead result 1 3 5 2 4 null Odd/even refers to POSITION (1-based), not value. Both chains keep their original relative order.
Iterodd.next =oddeven.next =evenGuard after
13344even=4, even.next=5 → continue
255nullnulleven = null → stop
endevenHead (2)———1→3→5→2→4
Java — complete solution with main()
public class OddEvenLinkedList { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Weave two chains in one pass: O(n) time, O(1) space static ListNode oddEvenList(ListNode head) { if (head == null) return null; ListNode odd = head, even = head.next, evenHead = even; while (even != null && even.next != null) { odd.next = even.next; // odd jumps over one even node odd = odd.next; even.next = odd.next; // even jumps over one odd node even = even.next; } odd.next = evenHead; // glue the even chain after the odd chain return head; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(oddEvenList(build(1, 2, 3, 4, 5)))); // [1,3,5,2,4] System.out.println(str(oddEvenList(build(2, 1, 3, 5, 6, 4, 7)))); // [2,3,6,7,1,5,4] System.out.println(str(oddEvenList(build(1, 2)))); // [1,2] } }
ApproachTimeSpaceNotes
Two new lists / array copyO(n)O(n)violates O(1) space
In-place weaveO(n)O(1)one pass
⚠ Common bugs & edge cases:
  • Confusing positions with values: [2,1,3,…] groups by index, not by parity of the number.
  • Losing evenHead — once even advances, the start of the even chain is unreachable.
  • Loop guard even != null && even.next != null handles both odd and even lengths; checking only odd.next breaks one of them.
12
Drill 49 · Pointer Switching

Intersection of Two Linked Lists

Drill 49 — Intersection of Two Linked Lists
Easypointer switchingLeetCode 160 ↗
Given the heads of two singly linked lists, return the node at which they intersect (the first node shared by reference), or null. The lists must keep their original structure; there are no cycles.
Example
Input: A = [4,1,8,4,5], B = [5,6,1,8,4,5], shared from node 8 Output: node with value 8 // the 1 in A and the 1 in B are DIFFERENT nodes with equal values Input: A = [2,6,4], B = [1,5] Output: null
Key insight: The lists differ only in their unique prefixes (a and b nodes). If pointer A walks list A then list B, and pointer B walks B then A, both travel a + b + c nodes before reaching the shared part a second time — so they arrive together. The null between the two laps is what makes the "no intersection" case terminate.
From brute force to optimal

Brute force compares every node of A with every node of B: O(n·m). A HashSet of A's nodes gives O(n+m) time but O(n) space. Length-difference alignment (advance the longer list by |n-m|, then walk together) is O(n+m)/O(1) but needs two counting passes. The head-switching trick gets the same bounds with no counting and five lines of code.

Walkthrough
Intersection at node 8: switching heads equalises the path lengths
A B 4 1 5 6 1 8 4 5 null shared tail (c = 3) a = 2 unique b = 3 unique pA walks: 4 1 8 4 5 null | 5 6 1 [8] (a + c + 1 + b = 9 steps) pB walks: 5 6 1 8 4 5 null | 4 1 [8] (b + c + 1 + a = 9 steps) Same distance travelled → both arrive at the first shared node on step 9. No intersection → both hit null together.
Java — complete solution with main()
public class IntersectionOfTwoLists { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Each pointer walks A + B (or B + A): equal total distance, so they // arrive at the shared node together, or both reach null. // O(n + m) time, O(1) space. static ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode a = headA, b = headB; while (a != b) { // reference comparison a = (a == null) ? headB : a.next; b = (b == null) ? headA : b.next; } return a; // shared node, or null } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static ListNode tailOf(ListNode head) { while (head.next != null) head = head.next; return head; } public static void main(String[] args) { ListNode shared = build(8, 4, 5); ListNode a = build(4, 1); ListNode b = build(5, 6, 1); tailOf(a).next = shared; // A = 4 -> 1 -> 8 -> 4 -> 5 tailOf(b).next = shared; // B = 5 -> 6 -> 1 -> 8 -> 4 -> 5 ListNode hit = getIntersectionNode(a, b); System.out.println(hit == null ? "null" : hit.val); // 8 ListNode c = build(2, 6, 4), d = build(1, 5); System.out.println(getIntersectionNode(c, d)); // null } }
ApproachTimeSpaceNotes
Nested loopsO(n·m)O(1)
HashSet of A's nodesO(n+m)O(n)
Align by length differenceO(n+m)O(1)two counting passes
Switch headsO(n+m)O(1)at most 2 laps each
⚠ Common bugs & edge cases:
  • Comparing val instead of references — the example deliberately contains equal values (1) on different nodes.
  • Switching to the other head when p.next == null (skipping the null step) loops forever when there is no intersection.
  • Modifying the lists (e.g. marking visited nodes) is not allowed — the structure must be restored.
13
Drill 50 · Two Chains

Partition List

Drill 50 — Partition List
Mediumtwo dummy chainsLeetCode 86 ↗
Given a linked list and a value x, rearrange it so that all nodes with value less than x come before nodes with value greater than or equal to x. Preserve the original relative order within each group.
Example
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5] Input: head = [2,1], x = 2 Output: [1,2]
Key insight: Do not try to swap nodes in place like array partitioning — that breaks stability. Instead deal the nodes into two piles (two dummy-headed chains), then stack the piles. Template A, twice.
From brute force to optimal

An array-based approach copies values out, stably partitions, and writes them back: O(n) time, O(n) space. Swapping-based in-place partition (Lomuto/Hoare) is not stable. Two chains reuse the existing nodes in a single pass: O(n) time, O(1) extra space, and stable by construction.

Walkthrough
Partition [1,4,3,2,5,2] around x = 3 with two dummy-headed chains
input, x = 3 1 <3 4 >=3 3 >=3 2 <3 5 >=3 2 <3 null less chain L 1 2 2 ge chain ge.next = null G 4 3 5 ge null less.next = geHead.next result 1 2 2 4 3 5 null Stable: 4 before 3 in the output because 4 came before 3 in the input. Last ge node (5) originally pointed at 2 — cut it.
Java — complete solution with main()
public class PartitionList { static class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } // Two dummy-headed chains, then concatenate: O(n) time, O(1) space. // Relative order inside each half is preserved (stable). static ListNode partition(ListNode head, int x) { ListNode lessHead = new ListNode(0), less = lessHead; ListNode geHead = new ListNode(0), ge = geHead; for (ListNode curr = head; curr != null; curr = curr.next) { if (curr.val < x) { less.next = curr; less = curr; } else { ge.next = curr; ge = curr; } } ge.next = null; // CRUCIAL: cut the old link or you may create a cycle less.next = geHead.next; // concatenate: [< x] then [>= x] return lessHead.next; } static ListNode build(int... vals) { ListNode dummy = new ListNode(0), tail = dummy; for (int v : vals) { tail.next = new ListNode(v); tail = tail.next; } return dummy.next; } static String str(ListNode head) { StringBuilder sb = new StringBuilder("["); for (ListNode n = head; n != null; n = n.next) { sb.append(n.val); if (n.next != null) sb.append(","); } return sb.append("]").toString(); } public static void main(String[] args) { System.out.println(str(partition(build(1, 4, 3, 2, 5, 2), 3))); // [1,2,2,4,3,5] System.out.println(str(partition(build(2, 1), 2))); // [1,2] System.out.println(str(partition(build(5, 6), 1))); // [5,6] } }
ApproachTimeSpaceNotes
Copy values, partition, write backO(n)O(n)
Two dummy chainsO(n)O(1)stable, one pass
⚠ Common bugs & edge cases:
  • Forgetting ge.next = null: the last >= node still points at an old successor, often creating a cycle (here 5 → 2).
  • Using <= for the left chain — the spec puts values equal to x on the right.
  • Returning lessHead instead of lessHead.next; if no node is < x, lessHead.next correctly becomes the ge chain.
14
Chapter Fourteen · Summary

All Eleven Drills at a Glance

Every drill on this page runs in linear time and — except for the newly created digits of Add Two Numbers — constant extra space. That is the signature of linked-list problems: the interviewer is not testing algorithmic cleverness so much as your ability to rewire references without losing any. If your solution allocates an array or a HashMap, there is almost always an O(1)-space pointer version they are waiting for.

#DrillPatternTimeSpaceDifficulty
40Reverse Linked Listin-place reversalO(n)O(1)Easy
41Merge Two Sorted Listsdummy + tailO(n+m)O(1)Easy
42Linked List Cyclefast & slowO(n)O(1)Easy
43Middle of the Linked Listfast & slowO(n)O(1)Easy
44Remove Nth Node From Enddummy + gapO(n)O(1)Medium
45Add Two Numberssimulation + dummyO(max(n,m))O(1) extraMedium
46Swap Nodes in Pairsdummy + rewiringO(n)O(1)Medium
47Rotate Listlength + ring + cutO(n)O(1)Medium
48Odd Even Linked Listsplit & weaveO(n)O(1)Medium
49Intersection of Two Listspointer switchingO(n+m)O(1)Easy
50Partition Listtwo dummy chainsO(n)O(1)Medium
Chapter recap — what to remember
  • Dummy node whenever the head can change or you are building output (41, 44, 45, 46, 50).
  • Fast & slow for middle and cycle (42, 43) — guard with fast != null && fast.next != null.
  • Gap pointers / length first for positions measured from the end (44, 47).
  • Save next before you overwrite it — reversal (40), swapping (46), weaving (48).
  • Compare references, not values for "same node" questions (42, 49).
  • Terminate output chains with tail.next = null to avoid stale links and cycles (47, 50).
What to practice next:
  • Combine templates: Palindrome Linked List (middle + reverse second half + compare), Reorder List (middle + reverse + weave), Sort List (middle + merge = merge sort), Linked List Cycle II (Floyd + reset to head).
  • Review the data structure itself on the Linked List guide and the runner technique in Two Pointers.
  • Full single-problem write-ups: LC 206, LC 21, LC 141, LC 19, LC 2; more practice in the LeetCode linked-list set.
  • Next page: 06 Binary Trees & BST — the same pointer discipline, but every node has two next references.