Linked List Problems

Seven classic interview problems — Reverse a Linked List, Merge Two Sorted Lists, Linked List Cycle, Remove Nth Node From End, Reorder List, LRU Cache and Merge K Sorted Lists — solved from zero with a handful of moves on boxes joined by arrows. For each problem you will see the slow obvious idea, the trick that fixes it, the pseudocode, the Dart code, and an animation you can feed your own input, with every node drawn as a box, every next link as an arrow, and every pointer (prev, curr, slow, fast, tail) as a label that moves. By the end you will know the four linked-list tools — the dummy head, two pointers, reversing links in place, and splitting and merging — and how to change links without ever losing the rest of the list.

Nodes, references and the four linked-list tools

Some words first:

• A node is one box. It holds a value (here a whole number, val) and a link called next: a way to find the node that comes after it.
• The head is the first node. If you have the head, you can reach every node by following next again and again. The last node is the tail; its next is null, which means "nothing comes after me".
• An empty list is simply a head that is null — there is no first node at all.
• Traversal means walking the list: start at the head and follow next until you reach null.
• O(1) means the work does not grow with the list; O(n) means it grows in step with the number of nodes n. See C03 · Growth of Functions.

A node in Dart

Interviews give you this class (or ask you to write it). ListNode? with a question mark means "a ListNode or null" — the tail's next must be allowed to be null. The two helpers below turn a plain Dart list like [4, 8, 15] into nodes and back; every test on this page uses them.

Notice what a linked list does not have: indexes. A Dart List keeps its items side by side in one block of memory, so list[1000] is found in one step. A linked list's nodes can be anywhere; the only way to reach node number 1000 is to follow 1000 arrows. In exchange, inserting or removing a node next to one you are already holding is O(1): you change one or two arrows and nothing else moves.

Dart itself ships a linked list in dart:collection: LinkedList (an intrusive, doubly linked list whose entries extend LinkedListEntry), and Queue/ListQueue for adding and removing at both ends — see D28 · Queue, ListQueue & LinkedList. Interviews still expect you to work with a hand-made ListNode, because the questions are about moving the arrows yourself. Linked lists built from scratch, with insert and delete, are in C10 · Linked lists.

What a "pointer" means in Dart

Interview problems talk about "pointers" (prev, curr, slow, fast). Dart has no pointer arithmetic, but every variable that holds an object holds a reference to it — an arrow to an object that lives on the heap (the shared storage room for objects). var curr = head; does not copy the node; it makes a second arrow to the same node. Moving curr (curr = curr.next) changes only where curr points. Changing a node through curr (curr.val = 20, curr.next = null) changes the one shared node, so everyone who can reach it sees the change. The whole story of references and copies is in D22 · Variables, objects and references.

The four tools

Almost every linked-list question is solved with one or two of these. Spot them and the plan writes itself.

1. The dummy head. A fake node placed in front of the real head (final dummy = ListNode(0, head)). Code that builds or deletes nodes no longer needs a special case for "the list is empty" or "the head itself changes" — the head is just dummy.next, and you return dummy.next at the end. (Merge Two Sorted Lists, Remove Nth Node, Merge K Lists.)
2. Two pointers. Two references walking the same list. Fast and slow: fast moves two nodes for each one of slow — when fast reaches the end, slow is in the middle, and if there is a loop, fast catches slow. A gap of n: start one pointer n nodes ahead and move both at the same speed — when the front one reaches the end, the back one is n nodes from the end. These are the slow/fast pointers of Step 13.2 · Remove Duplicates (slow and fast pointers), now on nodes instead of indexes. (Cycle, Remove Nth, Reorder.)
3. Reversing links in place. Walk the list and turn each next arrow around, keeping three references: the part already reversed (prev), the node being turned (curr), and the rest (nextNode), saved before the arrow is changed. (Reverse, Reorder, palindrome checks, reversing in groups.)
4. Splitting and merging. Cut a list into pieces by setting one next to null; join sorted pieces by repeatedly taking the smaller front node. (Merge Two, Reorder, Merge K, and merge sort on a list.)

The first tool on its own: build a list from values with a dummy head, then walk it. Watch the tail label: because the dummy exists from the start, "hang the new node after tail" works for the very first node too.

Draw before you code

Linked-list bugs are almost always "I changed an arrow too early and lost the rest of the list" or "I followed next from null". Both are caught on paper in a minute. Draw three or four boxes with arrows, write each pointer's name above its box, and then — before writing code — change the arrows one at a time with a pencil, crossing out the old arrow. For each change ask: after this line, can I still reach every node I need? Then run the drawing again on the tiny cases: an empty list, one node, two nodes.

Null safety: when next! is safe

Dart's sound null safety (D05 · Null Safety) is on your side here: node.next has the type ListNode?, so Dart refuses node.next.val until you deal with the null. You have three tools: ?. (stop and give null if the left side is null), ?? (a fallback value), and ! ("I promise this is not null" — and if you are wrong, Dart throws a TypeError at that moment).

One rule surprises everyone: Dart promotes a local variable after a null check (inside if (after != null), after has the type ListNode), but it does not promote a field like fast.next, because another piece of code could change a field between the check and the use. So after while (fast.next != null) you still write fast.next!. That ! is safe because you just checked — write a comment saying so. A ! you cannot justify with a check on the line before is a crash waiting to happen.

Reverse a Linked List

The task. You get the head of a singly linked list. Turn the list around so the last node becomes the first, and return the new head. Reuse the same nodes — change their next links, do not build new nodes.

Brute force. Copy the values into a Dart List and build a new list backwards, putting each new node in front of the ones already built. It is O(n) time, but it creates n new nodes (O(n) extra memory), and the task wants the original nodes reused.

Key insight. Walk once from the head. At each node curr, its arrow should point at the node before it, which is the head of the part already reversed, prev. But the moment you overwrite curr.next, you lose your only way to the rest of the list. So use three references, in this order: save nextNode = curr.next, turn curr.next = prev, step prev = curr; curr = nextNode.

Why it is correct. The invariant (a fact true at the start of every loop round): prev is the head of the already-reversed part (the nodes before curr, now pointing backwards), and curr is the head of the untouched rest. Each round moves exactly one node from the rest to the front of the reversed part. When curr is null the rest is empty, so prev is the head of the whole reversed list.

An edge case: two nodes. The loop runs twice; the first round already makes the first node the tail (its arrow now points at null).

The recursive version. Recursion (a function calling itself — D07 · Recursion) gives a short answer with a different shape. Trust the function to reverse everything after the head. When that call returns, the head's old neighbour second is now the tail of the reversed rest — so point second.next back at the head, and make the head the new tail. The base case: an empty list or a single node is already reversed.

Complexity. Iterative: time O(n) (each node is visited once and changed once), space O(1) (three references). Recursive: time O(n), but space O(n) for n waiting calls on the call stack — a list of 100 000 nodes can overflow the stack, which is why interviewers prefer the loop.

Follow-ups interviewers ask. Reverse only the nodes from position left to right (p06-q22). Reverse in groups of k (p06-q23). Check whether a list reads the same backwards — reverse the second half and compare (p06-q7). Do it recursively, and explain the stack cost.

The idea underneath: changing references, not values — D22 · Variables, objects and references — and the list operations of C10 · Linked lists.

Merge Two Sorted Lists

The task. You get the heads of two linked lists a and b, each sorted from small to large (equal values allowed). Join them into one sorted list by relinking their nodes, and return its head.

Brute force. Pour all values into one Dart List, sort it, and build new nodes. It works, but it ignores that both inputs are already sorted, costs O((n + m) log(n + m)), and allocates n + m new nodes.

Key insight. The smallest node overall is one of the two front nodes. Take it, attach it to the end of the answer, and advance in that list. Repeat. Building "the end of the answer" needs a reference to its last node, tail — and here the dummy head shines: start with tail = dummy, so attaching the very first node is the same line as attaching any other. The real head is dummy.next.

Why it is correct. Invariant: the list hanging off dummy holds the smallest nodes taken so far, in sorted order, and every node still in a or b is at least as big as tail. Taking the smaller front node keeps both facts true. When one list is empty, the other is sorted and every node in it is at least as big as tail, so it can be attached whole with a single link.

An edge case: a is empty. The loop never runs, and the last line attaches all of b after the dummy.

Complexity. Time O(n + m) — every comparison attaches one node, and the leftover is attached in one step. Space O(1) — one dummy node and a few references; no node is copied.

Follow-ups interviewers ask. Merge k lists instead of two (the last problem on this page). Sort a whole linked list with merge sort, which uses exactly this function (p06-q19, and in O(1) extra space p06-q25). Merge recursively: a.next = mergeTwoLists(a.next, b) — shorter, but O(n + m) stack.

The idea underneath: the merge step of merge sort in C02 · Divide and conquer: merge, done on arrows instead of array slots.

Linked List Cycle

The task. You get the head of a linked list. Return true if following next from the head ever comes back to a node it has already visited — the list has a cycle (a loop) — and false if it reaches null. In the examples, the tail is linked back to the node at index pos (−1 means no link back); your function never sees pos, only the head.

Brute force. Walk the list and remember every node you have stood on in a Set. If you step onto a node already in the set, there is a cycle; if you reach null, there is none. The set must compare nodes by identity — two different nodes holding the same value are different places — which Set.identity() guarantees. O(n) time, O(n) memory.

Key insight (Floyd's "tortoise and hare"). Move slow one node and fast two nodes per round. Without a cycle, fast reaches null after about n / 2 rounds. With a cycle, both pointers eventually go round the loop, and they must meet.

Why they must meet — and never jump over each other. Once both are inside the loop, measure how many steps fast is behind slow going round the loop; call it the gap, d. Each round slow moves 1 forward and fast moves 2, so the gap shrinks by exactly 1: d, d − 1, d − 2, …, 0. A gap that shrinks one at a time cannot skip 0, so fast lands exactly on slow. The gap is less than the loop length c when slow enters the loop, so they meet within c more rounds — at the latest just as slow completes its first lap. Total rounds: at most (nodes before the loop) + c, which is O(n).

An edge case: the cycle starts at the head (pos = 0), so the whole list is one loop and both pointers are inside it from the very first step.

Follow-up: where does the cycle start?

Interviewers almost always ask next: return the first node of the loop (or null). After slow and fast meet, start a new pointer a at the head and b at the meeting point, and move both one step at a time. They meet exactly at the start of the loop.

The distance argument. Let x be the number of nodes before the loop, c the loop length, and y how far into the loop (from its first node) the meeting happened. When they meet, slow has walked x + y steps and fast twice as many, 2(x + y). fast walked the same path plus some whole laps, k · c with k ≥ 1. So 2(x + y) = x + y + k·c, which gives x + y = k·c, so x = k·c − y. Read that sentence aloud: walking x steps from the meeting point is the same as walking c − y steps (to the loop's first node) plus k − 1 full laps — you end on the first node of the loop. And walking x steps from the head also ends there. So the two walkers, started at the head and at the meeting point, arrive at the loop's first node at the same moment.

Complexity. Time O(n) — fewer than x + c rounds to meet, and x more steps to find the start. Space O(1) — two or four references.

Follow-ups interviewers ask. The length of the loop: after meeting, walk once round and count (p06-q27). Find the duplicate number in an array of n + 1 values from 1 to n without changing it, in O(1) space — the same algorithm on "index i points to index nums[i]" (p06-q26). Why must fast move exactly 2? With speed 3 the gap shrinks by 2 each round, so on a loop of even length an odd gap is never 0 and the pointers can circle forever — with speed 2 the gap shrinks by exactly 1 and cannot miss (p06-q30).

The idea underneath: the slow/fast pointer pattern of Step 13.2 · Remove Duplicates (slow and fast pointers), and comparing objects by identity from D22 · identical().

Remove Nth Node From End

The task. You get the head of a linked list and a number n. Remove the n-th node counting from the end (n = 1 is the last node) and return the head of the changed list. Try to walk the list only once.

Brute force. Two passes: walk once to count the length L, then walk again L − n steps from a dummy node to stand just before the node to delete. This is O(L) already — the follow-up interviewers ask is "can you do it in one pass?"

Key insight. To delete a node in a singly linked list you must stand on the node before it (you change that node's next). Start two pointers, lead and trail, on a dummy node in front of the head. Move lead forward n nodes first. Then move both one step at a time until lead stands on the last node. The gap is still n, so trail is exactly one node before the n-th node from the end. Skip it: trail.next = trail.next.next.

Why the dummy is needed. If n equals the length, the node to delete is the head itself, and there is no real node before it. The dummy is that "node before", so the same skip line deletes the head — and we return dummy.next, the new head.

An edge case: n equals the length. trail never leaves the dummy, and the skip removes the head.

Complexity. Time O(L) — lead walks the list once and trail walks part of it. Space O(1).

Follow-ups interviewers ask. Return the k-th value from the end without deleting (p06-q10). Delete a node when you are given only that node and not the head (p06-q11 — copy the next node into it). Find the middle node in one pass (p06-q3 — a speed difference instead of a gap).

The idea underneath: two pointers with a fixed gap — the same "window of fixed size" idea as Step 13.3 · Sliding Window, measured in nodes.

Reorder List

The task. A list L0 → L1 → … → Ln−1 must be rearranged in place into L0 → Ln−1 → L1 → Ln−2 → L2 → …: first node, last node, second node, second-to-last node, and so on. Change the links only (not the values) and return nothing — the caller still holds the head.

Brute force. Put every node into a Dart List (now you have indexes!), then relink from both ends with two indexes moving toward each other. O(n) time, but O(n) extra memory for the list. An even slower idea — walking to the end to find the current last node for every step — is O(n²).

Key insight. The order needs the back half backwards, and a singly linked list can only walk forwards. So make the back half walk forwards: three tools in a row.

1. Find the middle with slow and fast pointers. Stop when fast cannot take two more steps; slow is then the last node of the first half (the first half is equal or one node longer).
2. Reverse the second half with reverseList from the first problem, and cut the list in two (slow.next = null).
3. Weave: take one node from the front half, then one from the reversed back half, and so on — a merge that alternates instead of comparing.

An edge case: two nodes. The middle is the first node, the back half is one node (reversing it changes nothing), and the single weave step rebuilds the same list.

Complexity. Time O(n) — about n / 2 rounds to find the middle, n / 2 to reverse, n / 2 to weave. Space O(1) — only references.

Follow-ups interviewers ask. Check whether a list is a palindrome in O(1) space — the same first two steps, then compare instead of weave (p06-q7). Group all odd-position nodes before even-position ones (p06-q13). Split a list in the middle for merge sort (p06-q19).

The idea underneath: three tools from this page combined — slow/fast (Step 13.2), in-place reversal (the first problem), and a merge (the second problem).

LRU Cache

The task. A cache is a small, fast store that keeps recently used data close at hand. Design a cache of a fixed capacity (at least 1) with two operations, each in O(1) average time: get(key) returns the value stored for key, or −1 if it is not there; put(key, value) stores the value (replacing an old one for the same key). When a put of a new key would go over capacity, first throw out the least recently used key — the one whose last get or put is oldest. LRU stands for exactly that.

Brute force. A map for the values plus a Dart List of keys in order of use. Each get must find the key in the list and move it to the end (remove is O(capacity)), and each eviction removes the first key (removeAt(0) shifts everything, O(capacity)).

Key insight. We need two things at once, each in O(1): find a key (a hash map does that — C11 · Hash Tables) and move any key to the front, or remove the oldest (a doubly linked list does that, if we already hold the node). So combine them: the map stores key → node, and the nodes form a doubly linked list — each node has prev and next — ordered from most to least recently used. Holding a node, we can unlink it in O(1) because it knows both neighbours; a singly linked list would need the node before it, which takes O(n) to find.

• Two sentinel nodes (fake nodes that are never removed) sit at the ends: head on the "most recent" side and tail on the "least recent" side. Every real node then always has a real prev and next, so unlinking and inserting need no ifs for "first node" or "last node" — the same trick as the dummy head.
• get: look the key up in the map. Missing → −1. Found → unlink the node and re-insert it right after head (it is now the most recent).
• put: if the key exists, update the value and move the node to the front. Otherwise, if the cache is full, the least recently used node is tail.prev: unlink it and delete its key from the map — which is why each node also stores its key. Then create the node, store it in the map, and insert it at the front.

An edge case: capacity 1. Every put of a new key evicts the only key there is, so the list never holds more than one real node.

The Dart shortcut: LinkedHashMap

Dart's default map — what {} creates — is a LinkedHashMap: a hash map that also remembers the order in which keys were inserted (D27 · Inside the three implementations). Inside, it pairs a hash table with a record of the insertion order — the same two-part idea as above. That gives a five-line LRU cache:

Two details make it work. First, updating the value of an existing key does not move it — map[1] = 100 keeps key 1 where it was — so get and put remove the key and insert it again, which puts it at the newest end. Second, the oldest key is keys.first.

When an interviewer will not accept it. If the question is "design an LRU cache", the interviewer wants to see that you can build the hash map + doubly linked list — the shortcut hides the whole point. The documentation promises the insertion order but not that every step (such as keys.first after many removals) costs O(1). And the hand-built version extends to variants the shortcut cannot do, such as LFU (least frequently used, p06-q29) or expiry times. Mention the shortcut, say why it works, and then build the real thing.

Complexity. get and put: O(1) average time — one hash lookup plus a constant number of arrow changes. Space O(capacity) — one map entry and one node per key.

Follow-ups interviewers ask. LFU — evict the least frequently used key, ties broken by least recent use (p06-q29). Design the doubly linked list on its own (p06-q21). Thread safety: wrap each operation in a lock in languages with shared-memory threads; Dart isolates do not share memory, so a cache lives inside one isolate (D22 · Mutability and isolates).

The idea underneath: hash tables (C11 · Hash Tables) plus doubly linked lists with sentinels (C10 · Linked lists); Dart's ordered map in D27.

Merge K Sorted Lists

The task. You get a list of k linked lists, each sorted from small to large. Merge all of them into one sorted linked list and return its head. Some lists may be empty, and k may be 0.

Brute force. Pour every value into one Dart List, sort it, and build new nodes: O(N log N) time and N new nodes. Another slow idea: merge list 0 with list 1, then the result with list 2, and so on — the early nodes are walked again in every merge, O(N·k) in total.

Key insight 1 — a min-heap of front nodes. The next node of the answer is the smallest of the k front nodes. A min-heap (a binary tree stored in a list, where every parent is at most its children, so the smallest sits at index 0 — C06 · The binary heap as an array) hands out the smallest of k items in O(log k) and takes a new one in O(log k). Put every non-empty list's head in the heap; then repeatedly pop the smallest node, attach it to the answer, and push the next node of its list.

Dart has no built-in heap. The core libraries (dart:core, dart:collection) have no priority queue. The collection package has HeapPriorityQueue, but interviews usually want plain Dart — so write a small one. It is about thirty lines and it is tested on hundreds of random pushes and pops in this page's verification program:

An edge case: some lists are empty. Only non-empty lists put a node in the heap; with k = 0 (no lists at all), the heap starts empty, the loop never runs, and the answer is dummy.next, which is null.

Key insight 2 — merge in pairs (divide and conquer). No heap needed: merge list 0 with list 1, list 2 with list 3, and so on, using mergeTwoLists. That halves the number of lists. Repeat until one list is left. Every round touches each of the N nodes once, and there are about log₂ k rounds.

Follow-ups interviewers ask. The lists are huge streams on disk: the heap needs only one node per stream in memory (an "external merge"). Find the k-th smallest value across the lists without merging everything: stop after k pops. The smallest range that includes a value from each list: keep the heap and also track the current maximum.

The idea underneath: heaps and priority queues (C06 · Priority queues), the merge step of C02 · mergeSort, and Merge Two Sorted Lists above.

Quiz

Interview questions

Variations and follow-ups of the seven problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a reference that works on plain Dart lists.

Cheat sheet

Draw boxes and arrows first, change one arrow at a time, and test 0, 1 and 2 nodes. A ! is fine only right after a check that proves it — a field like node.next is never promoted by Dart, a local variable is.