Linked Lists
Linked lists are the data structure that teaches you to think in pointers. Unlike arrays, linked lists store elements scattered across memory, connected by references. This makes insertion and deletion at a known position but sacrifices random access. In interviews, linked list problems test your ability to manipulate pointers without losing track of nodes — a skill that maps directly to pointer-heavy systems code.
This lesson is part of Module 1 (see the module index and the overview in Arrays & Strings). It goes from how a node sits in memory, through the half-dozen pointer patterns that solve nearly every list problem, to complete proofs for the ones that look like magic — Floyd's cycle detection above all. The capstone for the module, an LRU cache, is built on the doubly linked list developed here.
Why linked lists exist
In 1955–56 Allen Newell, Cliff Shaw and Herbert Simon needed a way to represent symbolic expressions of unpredictable size and shape for their Logic Theorist program, on machines with a few thousand words of memory. Pre-allocating arrays for every expression was impossible, so they invented the list structure of their IPL languages: cells that hold a value and the address of the next cell, allocated one at a time from a free pool. John McCarthy's Lisp (1958) made the cons cell the universal data structure. The idea's advantage was not speed — it was that structure could grow, shrink and be rearranged without ever moving existing data.
That remains the real reason to use a linked list today. Arrays are faster at almost everything a program does in bulk (scan, index, sort). Linked lists win in exactly the situations where not moving things matters: you hold a pointer to a node and need to unlink it in ; other structures hold pointers to your elements and must not be invalidated; memory is a pool of fixed-size blocks; or an element must sit on several lists at once. Those situations are common in operating systems, allocators, caches and language runtimes — which is why linked lists are rare in application code and everywhere in systems code.
Pattern triggers
| If the problem says… / has… | Think of | Why |
|---|---|---|
| "linked list" + "cycle", "loop", "does it terminate", "repeated state" | Floyd fast/slow pointers (or Brent) | Two speeds must meet inside any cycle; memory |
| "middle node", "split in half", "second half" | Fast/slow pointers | When fast reaches the end, slow is halfway |
| "k-th from the end", "remove nth from end", one pass | Two pointers with a gap | A fixed gap of turns "from the end" into "from the start" |
| "reverse", "reverse between m and n", "reverse in groups of k", "palindrome list" | In-place reversal with prev / curr / next | The only -space way to walk a singly linked list backwards |
| "head might change", "delete nodes with value x", "partition" | Dummy (sentinel) head | Removes the special case for the first node |
| "merge two sorted", "merge k sorted", "sort a linked list" | Merge with a tail pointer, heap for lists, bottom-up merge sort | Merging is natural on lists: no extra array, just relinking |
| "two lists that may share a tail", "intersection" | Length alignment or pointer switching | Equalising the remaining lengths makes the pointers arrive together |
| "deep copy" with extra random/arbitrary pointers | Hash map old → new, or the interleaving trick | Need a way to find each node's copy in |
| "O(1) get and put", "evict least recently used" | Doubly linked list + hash map | Map finds the node, list reorders it in |
| "digits stored in reverse order" | Carry propagation while walking both lists | Least significant digit first means addition order matches list order |
| "values 1..n in an array, find the duplicate, O(1) space" | Floyd on an implicit list (Arrays & Strings) | i → nums[i] is a linked list whose cycle entry is the duplicate |
Types of Linked Lists
graph LR
subgraph "Singly Linked List"
A1["1"] --> A2["2"] --> A3["3"] --> A4["null"]
end
graph LR
subgraph "Doubly Linked List"
B0["null"] <--> B1["1"] <--> B2["2"] <--> B3["3"] <--> B4["null"]
end
graph LR
subgraph "Circular Linked List"
C1["1"] --> C2["2"] --> C3["3"] --> C1
end
A singly linked list gives one-way traversal and the smallest node. A doubly linked list adds a prev pointer, buying deletion of a node you hold (you can reach its predecessor) and backward traversal, at the cost of one more pointer per node and twice as many pointer updates per splice. A circular list links the tail back to the head; with a single sentinel node it becomes the cleanest doubly linked list of all, because there is no null anywhere and every insertion or deletion is the same four assignments — this is exactly the shape of the Linux kernel's list_head.
Singly Linked List
Each node has a value and a next pointer. Traversal is one-way.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class SinglyLinkedList:
def __init__(self):
self.head = None
def prepend(self, val):
self.head = ListNode(val, self.head)
def append(self, val):
node = ListNode(val)
if not self.head:
self.head = node
return
current = self.head
while current.next:
current = current.next
current.next = node
def delete(self, val) -> bool:
if not self.head:
return False
if self.head.val == val:
self.head = self.head.next
return True
current = self.head
while current.next:
if current.next.val == val:
current.next = current.next.next
return True
current = current.next
return False
# --- self-check (same scenario in all four languages) ---
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
lst = SinglyLinkedList()
for v in (2, 3, 4):
lst.append(v)
lst.prepend(1)
assert to_list(lst.head) == [1, 2, 3, 4]
assert lst.delete(1) and to_list(lst.head) == [2, 3, 4] # delete head
assert lst.delete(3) and to_list(lst.head) == [2, 4] # delete middle
assert not lst.delete(99)
print("SinglyLinkedList OK")
import java.util.ArrayList;
import java.util.List;
public class SinglyLinkedListDemo {
static class ListNode {
int val;
ListNode next;
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
static class SinglyLinkedList {
ListNode head;
void prepend(int val) { head = new ListNode(val, head); }
void append(int val) {
ListNode node = new ListNode(val, null);
if (head == null) { head = node; return; }
ListNode cur = head;
while (cur.next != null) cur = cur.next;
cur.next = node;
}
boolean delete(int val) {
if (head == null) return false;
if (head.val == val) { head = head.next; return true; }
for (ListNode cur = head; cur.next != null; cur = cur.next) {
if (cur.next.val == val) { cur.next = cur.next.next; return true; }
}
return false;
}
}
static List<Integer> toList(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
SinglyLinkedList lst = new SinglyLinkedList();
for (int v : new int[]{2, 3, 4}) lst.append(v);
lst.prepend(1);
if (!toList(lst.head).equals(List.of(1, 2, 3, 4))) throw new AssertionError();
if (!lst.delete(1) || !toList(lst.head).equals(List.of(2, 3, 4))) throw new AssertionError();
if (!lst.delete(3) || !toList(lst.head).equals(List.of(2, 4))) throw new AssertionError();
if (lst.delete(99)) throw new AssertionError();
System.out.println("SinglyLinkedList OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
// Ownership via unique_ptr: destroying the list frees every node.
struct ListNode {
int val;
std::unique_ptr<ListNode> next;
explicit ListNode(int v, std::unique_ptr<ListNode> n = nullptr) : val(v), next(std::move(n)) {}
};
struct SinglyLinkedList {
std::unique_ptr<ListNode> head;
void prepend(int val) { head = std::make_unique<ListNode>(val, std::move(head)); }
void append(int val) {
std::unique_ptr<ListNode>* slot = &head; // pointer to the link we may fill
while (*slot) slot = &(*slot)->next;
*slot = std::make_unique<ListNode>(val);
}
bool remove(int val) {
for (std::unique_ptr<ListNode>* slot = &head; *slot; slot = &(*slot)->next) {
if ((*slot)->val == val) {
*slot = std::move((*slot)->next); // old node freed here
return true;
}
}
return false;
}
std::vector<int> values() const {
std::vector<int> out;
for (const ListNode* p = head.get(); p; p = p->next.get()) out.push_back(p->val);
return out;
}
};
int main() {
SinglyLinkedList lst;
for (int v : {2, 3, 4}) lst.append(v);
lst.prepend(1);
assert((lst.values() == std::vector<int>{1, 2, 3, 4}));
assert(lst.remove(1) && (lst.values() == std::vector<int>{2, 3, 4}));
assert(lst.remove(3) && (lst.values() == std::vector<int>{2, 4}));
assert(!lst.remove(99));
std::cout << "SinglyLinkedList OK\n";
}
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) {
this.val = val;
this.next = next;
}
}
class SinglyLinkedList<T> {
head: ListNode<T> | null = null;
prepend(val: T): void {
this.head = new ListNode(val, this.head);
}
append(val: T): void {
const node = new ListNode(val);
if (!this.head) {
this.head = node;
return;
}
let current = this.head;
while (current.next) current = current.next;
current.next = node;
}
delete(val: T): boolean {
if (!this.head) return false;
if (this.head.val === val) {
this.head = this.head.next;
return true;
}
let current = this.head;
while (current.next) {
if (current.next.val === val) {
current.next = current.next.next;
return true;
}
current = current.next;
}
return false;
}
}
// --- self-check ---
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
function toArr<T>(h: ListNode<T> | null): T[] { const out: T[] = []; for (; h; h = h.next) out.push(h.val); return out; }
const lst = new SinglyLinkedList<number>();
for (const v of [2, 3, 4]) lst.append(v);
lst.prepend(1);
check(JSON.stringify(toArr(lst.head)) === "[1,2,3,4]", "build");
check(lst.delete(1) && JSON.stringify(toArr(lst.head)) === "[2,3,4]", "delete head");
check(lst.delete(3) && JSON.stringify(toArr(lst.head)) === "[2,4]", "delete middle");
check(!lst.delete(99), "delete missing");
console.log("SinglyLinkedList OK");
The C++ version uses the pointer-to-link idiom (std::unique_ptr<ListNode>* slot): instead of tracking the previous node, track the address of the link that points at the current node. Deleting then needs no special case for the head, because the head is just another link. Linus Torvalds called this the difference between code with "good taste" and code with an if for the first element; it is the C/C++ cousin of the dummy-head trick.
Complexity Summary
| Operation | Singly | Doubly |
|---|---|---|
| Access by index | ||
| Prepend | ||
| Append (with tail pointer) | ||
| Insert after known node | ||
| Delete known node | * | |
| Search |
*Singly linked list deletion requires finding the previous node, which takes .
(There is a well-known exception: given a pointer to a node that is not the tail of a singly linked list, you can "delete" it in by copying the next node's value into it and unlinking the next node — LeetCode 237. It changes node identity, so any outside pointer to the next node is now dangling; useful as a puzzle, dangerous in real code.)
The Dummy Head Trick
Many linked list problems become cleaner when you create a dummy node that points to the head. This eliminates special-case handling for operations that might modify the head.
// fragment — these lines live inside a function body
const dummy = new ListNode(0);
dummy.next = head;
// ... work with dummy.next ...
return dummy.next; // the new head
The dummy is a sentinel: a node that holds no data and exists only so that every real node has a predecessor. Two flavours recur. A temporary dummy (the tip above) lives for the duration of one function: merge, partition, remove-elements, reverse-between. A permanent sentinel lives inside the data structure: the LRU cache below keeps permanent head and tail sentinels so _remove and _add_to_front never test for null, and the Linux list_head is circular with a single permanent sentinel. Both buy the same thing — a uniform case — and the cost is one allocation.
Memory layout: why lists lose to arrays (most of the time)
The big-O table above makes linked lists look competitive. Hardware says otherwise. Three effects compound (the background is in How Data Structures Live in Memory):
- Pointer chasing defeats the prefetcher. In an array, the address of element is known before element is loaded, so the CPU fetches many cache lines in parallel and the prefetcher streams ahead. In a list, the address of node is stored inside node ; the CPU cannot start the next load until the current one finishes. Every node is a serialised round-trip to wherever it lives — about 1 ns from L1, roughly 4 ns from L2, 10–40 ns from L3 and 80–100 ns from DRAM on current desktop and server parts. A scan of a cold million-node list can be one to two orders of magnitude slower than a scan of a million-element array.
- Per-node overhead. Measured for one
intpayload on 64-bit platforms:
| Representation | Bytes per element | Notes |
|---|---|---|
int[] (Java), std::vector<int> (C++) | 4 | Values inline, contiguous |
Python list of small ints | 8 per slot (+28 per distinct int object) | Array of pointers to boxed ints |
Custom Java node {int val; Node next;} | 24 | 12-byte header + 4 + 4, padded to 8 (compressed oops) |
java.util.LinkedList<Integer> | about 40 | 24-byte node (item, next, prev) + 16-byte Integer |
std::list<int> (libstdc++) | 24 + allocator header | Two pointers + int, padded; malloc adds 8–16 bytes |
Python node with __slots__ | 48 (+28 per int) | Measured with sys.getsizeof on CPython 3.14 |
- Fragmentation and allocation cost. Each node is a separate allocation. Allocators are fast (a thread-local free list pop), but nodes allocated at different times end up scattered across the heap, so even a list built in one go loses locality after churn. Compacting garbage collectors can improve this by copying reachable nodes next to each other in traversal order — one of the few cases where a GC makes lists faster.
The upshot: if you will mostly iterate or index, use an array. Bjarne Stroustrup's often-cited demonstration ("Why you should avoid linked lists", GoingNative 2012) inserted random numbers into a sorted sequence and then removed them by position: std::vector, despite shifting elements on every insert, beat std::list at every size measured, because finding the position is a linear scan and the scan dominates.
When linked lists win
- splice when you already hold the node. Unlinking a node from a doubly linked list or moving it to the front is four pointer writes, no matter how long the list is. The LRU cache relies on this: the hash map hands you the node, the list moves it.
- Stable addresses. Inserting into a list never moves existing nodes, so pointers and iterators held elsewhere stay valid.
std::listguarantees iterator stability;std::vectorinvalidates on reallocation. - Intrusive lists. The node pointers live inside the element (
struct task_struct { ...; struct list_head tasks; ... }), so linking needs no allocation and one object can be on several lists at once (a run queue and a wait queue). The Linux kernel'sinclude/linux/list.hdefinesstruct list_head { struct list_head *next, *prev; };, circular with a sentinel, and recovers the containing struct withcontainer_of/list_entry. Tasks, timers, inodes, device lists and countless driver structures use it. Boost.Intrusive provides the same in C++. - Free lists. A memory allocator threads unused blocks into a list through the blocks themselves, so tracking free memory costs zero extra bytes. Allocation pops the head, free pushes it. See Memory Allocators.
- Lock-free stacks and queues. Treiber stacks and Michael–Scott queues are linked lists updated with a single compare-and-swap on a head or tail pointer; an array cannot grow lock-free nearly as easily. See Lock-Free Programming.
- Persistent (immutable) sequences. Prepending to an immutable list shares the entire old list; functional languages (Lisp, Haskell, Clojure, OCaml) rely on this structural sharing.
Node representations per language
| Language | Idiomatic node | Who frees it | Notes |
|---|---|---|---|
| Python | class ListNode: __slots__ = ("val", "next") | Reference counting + cycle collector | __slots__ avoids a per-node __dict__; a cyclic list is reclaimed by the cycle GC, not refcounting |
| Java | static class Node { int val; Node next; } | Tracing GC | Make it a static nested class, or every node carries a hidden reference to the outer instance |
| C++ | struct Node { int val; Node* next; } or std::unique_ptr<Node> next | You (or unique_ptr) | unique_ptr chains destroy recursively: a million-node list can overflow the stack in the destructor, so long lists need an iterative destructor |
| TypeScript | class ListNode { val: number; next: ListNode | null } | Tracing GC | V8 gives all nodes created the same way the same hidden class, so field access stays fast |
| C (kernel) | struct list_head embedded in the payload | You | Intrusive, circular, sentinel-based |
Pattern 1: Fast & Slow Pointers (Floyd's Algorithm)
Two pointers move at different speeds. The slow pointer moves one step at a time, the fast pointer moves two steps. This technique solves multiple problems elegantly.
Cycle Detection
graph LR
N1["1"] --> N2["2"] --> N3["3"] --> N4["4"] --> N5["5"] --> N3
style N3 fill:#f96,stroke:#333
def has_cycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals, cycle_to=-1):
"""Build a list from vals; if cycle_to >= 0 the tail links back to that index."""
nodes = [ListNode(v) for v in vals]
for a, b in zip(nodes, nodes[1:]):
a.next = b
if nodes and cycle_to >= 0:
nodes[-1].next = nodes[cycle_to]
return nodes[0] if nodes else None
assert has_cycle(build([1, 2, 3, 4, 5, 6], cycle_to=2))
assert has_cycle(build([1], cycle_to=0)) # self-loop
assert not has_cycle(build([1, 2, 3, 4]))
assert not has_cycle(None)
print("has_cycle OK")
public class HasCycle {
static class ListNode { int val; ListNode next; ListNode(int v) { val = v; } }
static boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // reference equality, not value equality
}
return false;
}
static ListNode build(int[] vals, int cycleTo) {
if (vals.length == 0) return null;
ListNode[] nodes = new ListNode[vals.length];
for (int i = 0; i < vals.length; i++) nodes[i] = new ListNode(vals[i]);
for (int i = 0; i + 1 < vals.length; i++) nodes[i].next = nodes[i + 1];
if (cycleTo >= 0) nodes[vals.length - 1].next = nodes[cycleTo];
return nodes[0];
}
public static void main(String[] args) {
if (!hasCycle(build(new int[]{1, 2, 3, 4, 5, 6}, 2))) throw new AssertionError();
if (!hasCycle(build(new int[]{1}, 0))) throw new AssertionError();
if (hasCycle(build(new int[]{1, 2, 3, 4}, -1))) throw new AssertionError();
if (hasCycle(null)) throw new AssertionError();
System.out.println("hasCycle OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
bool hasCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
// Owns the nodes (so cyclic lists are still freed) and links them.
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals, int cycleTo = -1) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
if (!nodes.empty() && cycleTo >= 0) nodes.back()->next = nodes[cycleTo].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
int main() {
Pool p;
assert(hasCycle(p.build({1, 2, 3, 4, 5, 6}, 2)));
assert(hasCycle(p.build({1}, 0)));
assert(!hasCycle(p.build({1, 2, 3, 4})));
assert(!hasCycle(nullptr));
std::cout << "hasCycle OK\n";
}
function hasCycle(head: ListNode<number> | null): boolean {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null = null;
constructor(val: T) { this.val = val; }
}
function build(vals: number[], cycleTo = -1): ListNode<number> | null {
const nodes = vals.map(v => new ListNode(v));
for (let i = 0; i + 1 < nodes.length; i++) nodes[i].next = nodes[i + 1];
if (nodes.length && cycleTo >= 0) nodes[nodes.length - 1].next = nodes[cycleTo];
return nodes[0] ?? null;
}
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(hasCycle(build([1, 2, 3, 4, 5, 6], 2)), "cycle");
check(hasCycle(build([1], 0)), "self-loop");
check(!hasCycle(build([1, 2, 3, 4])), "no cycle");
check(!hasCycle(null), "empty");
console.log("hasCycle OK");
Why it works: If there is a cycle, the fast pointer will eventually "lap" the slow pointer inside the cycle. If there is no cycle, the fast pointer reaches null.
Complexity: time, space.
Finding the Cycle Start
Once the fast and slow pointers meet inside the cycle, reset one pointer to the head and move both at the same speed. They will meet at the cycle start.
Mathematical proof: Let be the distance from head to cycle start, be the cycle length, and be the distance from cycle start to meeting point.
When they meet:
- Slow traveled:
- Fast traveled: for some integer
- Fast travels twice as far:
- Therefore: , which means
So starting one pointer at head and one at the meeting point, both moving one step, they will meet at the cycle start after steps.
def detect_cycle_start(head: ListNode | None) -> ListNode | None:
slow = fast = head
# Phase 1: Find meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
# Phase 2: Find cycle start
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals, cycle_to=-1):
nodes = [ListNode(v) for v in vals]
for a, b in zip(nodes, nodes[1:]):
a.next = b
if nodes and cycle_to >= 0:
nodes[-1].next = nodes[cycle_to]
return nodes[0] if nodes else None
assert detect_cycle_start(build([1, 2, 3, 4, 5, 6], cycle_to=2)).val == 3
assert detect_cycle_start(build([1, 2], cycle_to=0)).val == 1
assert detect_cycle_start(build([7], cycle_to=0)).val == 7
assert detect_cycle_start(build([1, 2, 3])) is None
print("detect_cycle_start OK")
public class DetectCycleStart {
static class ListNode { int val; ListNode next; ListNode(int v) { val = v; } }
static ListNode detectCycleStart(ListNode head) {
ListNode slow = head, fast = head;
while (true) { // phase 1: meet inside the cycle
if (fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head; // phase 2: both at speed 1
while (slow != fast) { slow = slow.next; fast = fast.next; }
return slow;
}
static ListNode build(int[] vals, int cycleTo) {
ListNode[] nodes = new ListNode[vals.length];
for (int i = 0; i < vals.length; i++) nodes[i] = new ListNode(vals[i]);
for (int i = 0; i + 1 < vals.length; i++) nodes[i].next = nodes[i + 1];
if (cycleTo >= 0) nodes[vals.length - 1].next = nodes[cycleTo];
return nodes[0];
}
public static void main(String[] args) {
if (detectCycleStart(build(new int[]{1, 2, 3, 4, 5, 6}, 2)).val != 3) throw new AssertionError();
if (detectCycleStart(build(new int[]{1, 2}, 0)).val != 1) throw new AssertionError();
if (detectCycleStart(build(new int[]{7}, 0)).val != 7) throw new AssertionError();
if (detectCycleStart(build(new int[]{1, 2, 3}, -1)) != null) throw new AssertionError();
System.out.println("detectCycleStart OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* detectCycleStart(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (true) { // phase 1
if (!fast || !fast->next) return nullptr;
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
slow = head; // phase 2
while (slow != fast) { slow = slow->next; fast = fast->next; }
return slow;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals, int cycleTo = -1) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
if (!nodes.empty() && cycleTo >= 0) nodes.back()->next = nodes[cycleTo].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
int main() {
Pool p;
assert(detectCycleStart(p.build({1, 2, 3, 4, 5, 6}, 2))->val == 3);
assert(detectCycleStart(p.build({1, 2}, 0))->val == 1);
assert(detectCycleStart(p.build({7}, 0))->val == 7);
assert(detectCycleStart(p.build({1, 2, 3})) == nullptr);
std::cout << "detectCycleStart OK\n";
}
function detectCycleStart(head: ListNode<number> | null): ListNode<number> | null {
let slow = head;
let fast = head;
// Phase 1: Find meeting point
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (fast === null || fast.next === null) return null;
// Phase 2: Find cycle start
slow = head;
while (slow !== fast) {
slow = slow!.next;
fast = fast!.next;
}
return slow;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null = null;
constructor(val: T) { this.val = val; }
}
function build(vals: number[], cycleTo = -1): ListNode<number> | null {
const nodes = vals.map(v => new ListNode(v));
for (let i = 0; i + 1 < nodes.length; i++) nodes[i].next = nodes[i + 1];
if (nodes.length && cycleTo >= 0) nodes[nodes.length - 1].next = nodes[cycleTo];
return nodes[0] ?? null;
}
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(detectCycleStart(build([1, 2, 3, 4, 5, 6], 2))!.val === 3, "start 3");
check(detectCycleStart(build([1, 2], 0))!.val === 1, "start 1");
check(detectCycleStart(build([7], 0))!.val === 7, "self-loop");
check(detectCycleStart(build([1, 2, 3])) === null, "no cycle");
console.log("detectCycleStart OK");
Floyd's algorithm: the complete proof
The short proof above is correct but leaves three questions open: why must the pointers meet at all, how long does it take, and why does the meeting point land exactly steps from the cycle start even when the tail is longer than the cycle. Here is the whole argument. The algorithm is attributed to Robert Floyd (Knuth credits it to him in TAOCP Vol. 2, §3.1, exercise 6), though Floyd never published it as a paper.
Setup. Number the nodes by their distance from the head along next. The list has a tail of nodes (positions ) followed by a cycle of nodes (positions , with the last linking back to position ). After steps the slow pointer is at position "unrolled", and the fast pointer at . A position corresponds to cycle offset .
Lemma 1 (no cycle ⇒ terminate). Without a cycle, fast reaches null after at most iterations; the loop condition fast and fast.next stops it. Slow never overtakes fast, so slow never dereferences null.
Lemma 2 (cycle ⇒ meet, and within steps). After steps slow enters the cycle at offset 0. Fast has been in the cycle for at least as long, at some offset (it is positions further along). From then on, each step increases fast's offset by 2 and slow's by 1, so the gap (fast's offset minus slow's, mod ) decreases by exactly 1 per step when measured as "how far fast is behind slow", i.e. steps close it (or steps if and we exclude step 0). Because the gap shrinks by one each time it can never jump over zero: the pointers cannot "skip past" each other. They meet within at most steps after slow enters the cycle, so the first meeting happens at some step . In particular slow completes less than one full lap before the meeting, a fact the next lemma uses.
Lemma 3 (the meeting step is a multiple of ). At the meeting step , both pointers are on the same node, so the difference in distance travelled, , is a whole number of laps: for some integer . Write the meeting point's offset into the cycle as (with by Lemma 2). Then
Theorem (phase 2 finds the entry). Put pointer at the head and at the meeting point and step both once per iteration. After exactly steps, is at position , the cycle entry. started at offset and has moved steps around the cycle, so its offset is — also the entry. Before step , is still in the tail and is in the cycle, so they cannot coincide earlier. Hence the first node where they meet is the cycle entry.
This version handles naturally: simply goes around the cycle extra times while walks the long tail. The original proof's "" is the same statement; the congruence form makes clear that only matters for where ends up.
Bound on total work. Phase 1 takes at most iterations (Lemma 2), phase 2 exactly , so the algorithm makes at most slow steps and pointer reads overall, with two pointers of state. The cycle length itself, if you need it, is one more lap from the meeting point: walk until you return, counting steps.
flowchart LR
H["head (pos 0)"] --> T1["pos 1"] --> E["entry (pos F)"]
E --> C1["offset 1"] --> M["meeting (offset a)"] --> C3["offset a+1"] --> E
subgraph phase2 ["Phase 2: both move 1 step"]
P1["p1 from head: F steps"] -.-> E
P2["p2 from meeting: F steps = -a mod C"] -.-> E
end
Trace: Floyd on 1→2→3→4→5→6→3
Here node 6 links back to node 3, so (nodes 1 and 2 are the tail) and (nodes 3, 4, 5, 6). Computed by script:
| step | slow | fast | slow == fast? |
|---|---|---|---|
| 0 | 1 | 1 | start |
| 1 | 2 | 3 | no |
| 2 | 3 | 5 | no |
| 3 | 4 | 3 | no |
| 4 | 5 | 5 | yes — meet |
They meet at node 5 after steps. Slow travelled 4, fast 8; the difference 4 is exactly one lap (). The meeting offset is (node 5 is two steps past the entry), and indeed .
Phase 2:
| step | p1 (from head) | p2 (from meeting) | equal? |
|---|---|---|---|
| 0 | 1 | 5 | no |
| 1 | 2 | 6 | no |
| 2 | 3 | 3 | yes — cycle start |
After steps both pointers reach node 3. Phase 1 used 4 iterations, within the bound.
Brent's algorithm (a variation)
Richard Brent's 1980 algorithm ("An improved Monte Carlo factorization algorithm", BIT 20) uses a different schedule. The hare moves one step at a time; the tortoise stays put and "teleports" to the hare's position whenever the number of steps since the last teleport reaches a power of two. If the hare ever lands on the tortoise, the number of steps since the last teleport is exactly the cycle length . Then the start is found by placing one pointer steps ahead of the other at the head and advancing both until they meet.
Trace on the same list (computed by script; power is the current window, lam the steps since the last teleport):
| step | power | lam | tortoise | hare | event |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 2 | start |
| 2 | 2 | 1 | 2 | 3 | teleport tortoise to hare, double power |
| 3 | 2 | 2 | 2 | 4 | |
| 4 | 4 | 1 | 4 | 5 | teleport tortoise to hare, double power |
| 5 | 4 | 2 | 4 | 6 | |
| 6 | 4 | 3 | 4 | 3 | |
| 7 | 4 | 4 | 4 | 4 | meet: lam = cycle length = 4 |
Then (start node 3), found by a second pass with a gap of 4.
Why bother? Each step of Brent's evaluates the next-function once (only the hare moves), while Floyd evaluates it three times per step (once for slow, twice for fast). When "next" is cheap (a pointer) the difference is small; when "next" is expensive — a hash, a modular multiplication in Pollard's rho factorisation, a step of a pseudo-random generator — it matters. Brent reported that his method is on average about 36% faster than Floyd's for cycle finding and sped up Pollard rho by about 24%. It also returns directly.
def brent(f, x0):
"""Return (mu, lam): tail length and cycle length of x0, f(x0), f(f(x0)), ..."""
power = lam = 1
tortoise, hare = x0, f(x0)
while tortoise != hare:
if power == lam: # start a new power-of-two window
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
tortoise = hare = x0 # find mu: hare starts lam steps ahead
for _ in range(lam):
hare = f(hare)
mu = 0
while tortoise != hare:
tortoise, hare = f(tortoise), f(hare)
mu += 1
return mu, lam
# The list 1->2->3->4->5->6->3 as a function on labels.
nxt = {1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 3}
assert brent(nxt.__getitem__, 1) == (2, 4)
# A pseudo-random sequence: x -> (x*x + 1) mod 255, the kind of map Pollard rho iterates.
mu, lam = brent(lambda x: (x * x + 1) % 255, 3)
seq, seen = [3], {3: 0}
while True:
nxt_val = (seq[-1] ** 2 + 1) % 255
if nxt_val in seen:
assert (seen[nxt_val], len(seq) - seen[nxt_val]) == (mu, lam)
break
seen[nxt_val] = len(seq)
seq.append(nxt_val)
print("brent OK", mu, lam)
Other variants: Gosper's algorithm (HAKMEM item 132) keeps a logarithmic table of previous values; Nivasch's stack algorithm (2004) finds the cycle with a stack whose expected size is logarithmic and stops within one cycle length of the entry. For linked lists in interviews, Floyd is the expected answer; mention Brent when the interviewer asks about cost per step.
Finding the Middle Node
The slow pointer will be at the middle when the fast pointer reaches the end.
def find_middle(head: ListNode | None) -> ListNode | None:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
assert find_middle(build([1, 2, 3, 4, 5])).val == 3
assert find_middle(build([1, 2, 3, 4, 5, 6])).val == 4 # right-middle for even length
assert find_middle(build([1])).val == 1
assert find_middle(None) is None
print("find_middle OK")
public class FindMiddle {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // right-middle for even lengths
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
public static void main(String[] args) {
if (findMiddle(build(1, 2, 3, 4, 5)).val != 3) throw new AssertionError();
if (findMiddle(build(1, 2, 3, 4, 5, 6)).val != 4) throw new AssertionError();
if (findMiddle(build(1)).val != 1) throw new AssertionError();
if (findMiddle(null) != null) throw new AssertionError();
System.out.println("findMiddle OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* findMiddle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow; // right-middle for even lengths
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
int main() {
Pool p;
assert(findMiddle(p.build({1, 2, 3, 4, 5}))->val == 3);
assert(findMiddle(p.build({1, 2, 3, 4, 5, 6}))->val == 4);
assert(findMiddle(p.build({1}))->val == 1);
assert(findMiddle(nullptr) == nullptr);
std::cout << "findMiddle OK\n";
}
function findMiddle(head: ListNode<number> | null): ListNode<number> | null {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow!.next;
fast = fast.next.next;
}
return slow; // middle node (right-middle for even-length lists)
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(findMiddle(build([1, 2, 3, 4, 5]))!.val === 3, "odd");
check(findMiddle(build([1, 2, 3, 4, 5, 6]))!.val === 4, "even");
check(findMiddle(build([1]))!.val === 1, "single");
check(findMiddle(null) === null, "empty");
console.log("findMiddle OK");
If you need the left-middle for even lengths (common when splitting a list for merge sort, so that the left half is never longer), start fast at head.next instead of head. With [1, 2, 3, 4] that returns node 2, and cutting after it gives halves [1, 2] and [3, 4]. Starting both at head returns node 3 and cutting after the middle would give [1, 2, 3] and [4] — still correct for merge sort, but on a two-node list it returns the second node and cutting after it yields an empty right half and infinite recursion. That is the single most common bug in recursive linked-list merge sort.
Pattern 2: Linked List Reversal
Reversal is the single most important linked list operation. It appears as a sub-problem in many harder questions.
Iterative Reversal
graph LR
subgraph "Before"
A1["1"] --> A2["2"] --> A3["3"] --> A4["null"]
end
graph RL
subgraph "After"
B4["null"] --- B3["3"] --> B2["2"] --> B1["1"]
end
def reverse_list(head: ListNode | None) -> ListNode | None:
prev = None
current = head
while current:
next_node = current.next # save next
current.next = prev # reverse pointer
prev = current # advance prev
current = next_node # advance current
return prev
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(reverse_list(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert values(reverse_list(build([1]))) == [1]
assert reverse_list(None) is None
print("reverse_list OK")
import java.util.ArrayList;
import java.util.List;
public class ReverseList {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next; // save next
cur.next = prev; // reverse pointer
prev = cur; // advance prev
cur = next; // advance current
}
return prev;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static List<Integer> values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
if (!values(reverseList(build(1, 2, 3, 4, 5))).equals(List.of(5, 4, 3, 2, 1))) throw new AssertionError();
if (!values(reverseList(build(1))).equals(List.of(1))) throw new AssertionError();
if (reverseList(null) != null) throw new AssertionError();
System.out.println("reverseList OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next; // save next
cur->next = prev; // reverse pointer
prev = cur; // advance prev
cur = next; // advance current
}
return prev;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(reverseList(p.build({1, 2, 3, 4, 5}))) == std::vector<int>{5, 4, 3, 2, 1}));
assert((values(reverseList(p.build({1}))) == std::vector<int>{1}));
assert(reverseList(nullptr) == nullptr);
std::cout << "reverseList OK\n";
}
function reverseList(head: ListNode<number> | null): ListNode<number> | null {
let prev: ListNode<number> | null = null;
let current = head;
while (current !== null) {
const next = current.next; // save next
current.next = prev; // reverse pointer
prev = current; // advance prev
current = next; // advance current
}
return prev;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode<number> | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(reverseList(build([1, 2, 3, 4, 5])))) === "[5,4,3,2,1]", "reverse 5");
check(JSON.stringify(values(reverseList(build([1])))) === "[1]", "reverse 1");
check(reverseList(null) === null, "reverse empty");
console.log("reverseList OK");
Complexity: time, space.
Invariant. At the top of each iteration, prev is the head of the already-reversed prefix (the nodes visited so far, in reverse order, ending in null), and current is the head of the untouched suffix. The two lists are disjoint and together contain every node. Each iteration moves one node from the front of the suffix to the front of the reversed prefix; when the suffix is empty, prev is the whole reversed list. The next_node save is mandatory: the line current.next = prev destroys the only reference to the rest of the list.
Trace on 1 → 2 → 3 → 4 → 5 (state after each iteration):
| step | node moved | next saved | prev after | current after | reversed part | remaining |
|---|---|---|---|---|---|---|
| 0 | - | - | null | 1 | (empty) | 1→2→3→4→5 |
| 1 | 1 | 2 | 1 | 2 | 1→null | 2→3→4→5 |
| 2 | 2 | 3 | 2 | 3 | 2→1→null | 3→4→5 |
| 3 | 3 | 4 | 3 | 4 | 3→2→1→null | 4→5 |
| 4 | 4 | 5 | 4 | 5 | 4→3→2→1→null | 5 |
| 5 | 5 | null | 5 | null | 5→4→3→2→1→null | (empty) |
Recursive Reversal
def reverse_list_recursive(head: ListNode | None) -> ListNode | None:
if not head or not head.next:
return head
new_head = reverse_list_recursive(head.next)
head.next.next = head # reverse the pointer
head.next = None # prevent cycle
return new_head
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(reverse_list_recursive(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert values(reverse_list_recursive(build([1]))) == [1]
assert reverse_list_recursive(None) is None
print("reverse_list_recursive OK")
import java.util.ArrayList;
import java.util.List;
public class ReverseListRecursive {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode reverse(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverse(head.next);
head.next.next = head; // reverse the pointer
head.next = null; // prevent cycle
return newHead;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static List<Integer> values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
if (!values(reverse(build(1, 2, 3, 4, 5))).equals(List.of(5, 4, 3, 2, 1))) throw new AssertionError();
if (!values(reverse(build(1))).equals(List.of(1))) throw new AssertionError();
if (reverse(null) != null) throw new AssertionError();
System.out.println("reverseRecursive OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* reverseRecursive(ListNode* head) {
if (!head || !head->next) return head;
ListNode* newHead = reverseRecursive(head->next);
head->next->next = head; // reverse the pointer
head->next = nullptr; // prevent cycle
return newHead;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(reverseRecursive(p.build({1, 2, 3, 4, 5}))) == std::vector<int>{5, 4, 3, 2, 1}));
assert((values(reverseRecursive(p.build({1}))) == std::vector<int>{1}));
assert(reverseRecursive(nullptr) == nullptr);
std::cout << "reverseRecursive OK\n";
}
function reverseListRecursive(head: ListNode<number> | null): ListNode<number> | null {
if (head === null || head.next === null) return head;
const newHead = reverseListRecursive(head.next);
head.next.next = head; // reverse the pointer
head.next = null; // prevent cycle
return newHead;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode<number> | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(reverseListRecursive(build([1, 2, 3, 4, 5])))) === "[5,4,3,2,1]", "reverse 5");
check(JSON.stringify(values(reverseListRecursive(build([1])))) === "[1]", "reverse 1");
check(reverseListRecursive(null) === null, "reverse empty");
console.log("reverseListRecursive OK");
Complexity: time, space (call stack).
Why it is correct (induction on length). For lengths 0 and 1 the list is its own reverse. For a longer list head → rest, assume the recursive call correctly reverses rest and returns its new head; the old head.next (the first node of rest) is now the tail of the reversed rest. Pointing that tail back at head and setting head.next = None appends head to the end. The head.next = None line is not cosmetic: without it the original first node still points at the second, and the result contains a two-node cycle.
The stack is the catch. CPython's default recursion limit is 1000 (sys.getrecursionlimit()), so the recursive version raises RecursionError on a 1,000-node list. On our test machine (OpenJDK 21, default thread stack size) the Java version handled 10,000 nodes but threw StackOverflowError at 20,000; the exact threshold depends on -Xss, the JIT and frame size, so treat it as "low tens of thousands". C++ has no guard at all — a deep enough list simply crashes. Use the iterative version for anything that is not known to be short.
Reverse Between Positions
Reverse only the sublist from position left to position right:
def reverse_between(head: ListNode | None, left: int, right: int) -> ListNode | None:
dummy = ListNode(0)
dummy.next = head
prev = dummy
for _ in range(left - 1):
prev = prev.next
current = prev.next
for _ in range(right - left):
next_node = current.next
current.next = next_node.next
next_node.next = prev.next
prev.next = next_node
return dummy.next
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(reverse_between(build([1, 2, 3, 4, 5]), 2, 4)) == [1, 4, 3, 2, 5]
assert values(reverse_between(build([1, 2, 3, 4, 5]), 1, 5)) == [5, 4, 3, 2, 1] # head changes
assert values(reverse_between(build([5]), 1, 1)) == [5]
print("reverse_between OK")
import java.util.ArrayList;
import java.util.List;
public class ReverseBetween {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
for (int i = 1; i < left; i++) prev = prev.next; // node before the sublist
ListNode cur = prev.next; // becomes the sublist's tail
for (int i = 0; i < right - left; i++) { // head-insertion
ListNode next = cur.next;
cur.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static List<Integer> values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
if (!values(reverseBetween(build(1, 2, 3, 4, 5), 2, 4)).equals(List.of(1, 4, 3, 2, 5))) throw new AssertionError();
if (!values(reverseBetween(build(1, 2, 3, 4, 5), 1, 5)).equals(List.of(5, 4, 3, 2, 1))) throw new AssertionError();
if (!values(reverseBetween(build(5), 1, 1)).equals(List.of(5))) throw new AssertionError();
System.out.println("reverseBetween OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
for (int i = 1; i < left; ++i) prev = prev->next;
ListNode* cur = prev->next;
for (int i = 0; i < right - left; ++i) { // head-insertion
ListNode* next = cur->next;
cur->next = next->next;
next->next = prev->next;
prev->next = next;
}
return dummy.next;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(reverseBetween(p.build({1, 2, 3, 4, 5}), 2, 4)) == std::vector<int>{1, 4, 3, 2, 5}));
assert((values(reverseBetween(p.build({1, 2, 3, 4, 5}), 1, 5)) == std::vector<int>{5, 4, 3, 2, 1}));
assert((values(reverseBetween(p.build({5}), 1, 1)) == std::vector<int>{5}));
std::cout << "reverseBetween OK\n";
}
function reverseBetween(
head: ListNode<number> | null,
left: number,
right: number
): ListNode<number> | null {
const dummy = new ListNode(0);
dummy.next = head;
// Find the node before the reversal starts
let prev: ListNode<number> = dummy;
for (let i = 1; i < left; i++) {
prev = prev.next!;
}
// Reverse the sublist
let current = prev.next!;
for (let i = 0; i < right - left; i++) {
const next = current.next!;
current.next = next.next;
next.next = prev.next;
prev.next = next;
}
return dummy.next;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode<number> | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(reverseBetween(build([1, 2, 3, 4, 5]), 2, 4))) === "[1,4,3,2,5]", "2..4");
check(JSON.stringify(values(reverseBetween(build([1, 2, 3, 4, 5]), 1, 5))) === "[5,4,3,2,1]", "1..5");
check(JSON.stringify(values(reverseBetween(build([5]), 1, 1))) === "[5]", "single");
console.log("reverseBetween OK");
This is the head-insertion form of reversal: prev stays fixed (the node just before the sublist) and current stays fixed (the original first node of the sublist, which drifts towards the end as nodes are moved in front of it). Each iteration plucks the node after current and inserts it right after prev. Invariant: after iteration , the first nodes of the sublist are reversed and sit between prev and current.next; current is the tail of the reversed part and still points at the unreversed remainder. Trace for [1, 2, 3, 4, 5], left = 2, right = 4:
| iteration | list | comment |
|---|---|---|
| 0 | 1→2→3→4→5 | prev = node 1, current = node 2 |
| 1 | 1→3→2→4→5 | moved 3 to just after prev |
| 2 | 1→4→3→2→5 | moved 4 to just after prev |
Exactly right − left iterations, each four pointer assignments, time and space. The dummy matters when left = 1: then prev is the dummy and the head of the list changes.
Reverse in groups of k
Reverse every consecutive block of k nodes; a final block shorter than k stays as is (LeetCode 25). It combines three ideas: count ahead to see whether a full group exists, reverse exactly k nodes with the iterative loop, and stitch the reversed group between the previous group's tail and the next group's head. A dummy head removes the special case for the first group.
Invariant. Before processing a group, group_prev is the last node of the already-finished output (initially the dummy), and group_prev.next is the first node of the unprocessed remainder. After reversing a full group, the group's old first node is its new last node; it becomes the next group_prev.
Trace for [1..8], k = 3:
| group | nodes | action | output so far |
|---|---|---|---|
| 1 | [1, 2, 3] | full group: reverse | [3, 2, 1] |
| 2 | [4, 5, 6] | full group: reverse | [3, 2, 1, 6, 5, 4] |
| 3 | [7, 8] | fewer than k: keep order | [3, 2, 1, 6, 5, 4, 7, 8] |
The implementation is in the canonical code group below. Each node is visited twice (once by the look-ahead count, once by the reversal), so it is time and space. The recursive formulation is shorter but uses stack.
Pattern 3: Merge Lists
Merge Two Sorted Lists
def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(merge_two_lists(build([1, 3, 5]), build([2, 4, 6]))) == [1, 2, 3, 4, 5, 6]
assert values(merge_two_lists(build([1, 2, 4]), build([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
assert values(merge_two_lists(None, build([0]))) == [0]
assert merge_two_lists(None, None) is None
print("merge_two_lists OK")
import java.util.ArrayList;
import java.util.List;
public class MergeTwoLists {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0, null), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } // <= keeps it stable
else { tail.next = l2; l2 = l2.next; }
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static List<Integer> values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
if (!values(merge(build(1, 3, 5), build(2, 4, 6))).equals(List.of(1, 2, 3, 4, 5, 6))) throw new AssertionError();
if (!values(merge(build(1, 2, 4), build(1, 3, 4))).equals(List.of(1, 1, 2, 3, 4, 4))) throw new AssertionError();
if (!values(merge(null, build(0))).equals(List.of(0))) throw new AssertionError();
if (merge(null, null) != null) throw new AssertionError();
System.out.println("mergeTwoLists OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
else { tail->next = l2; l2 = l2->next; }
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes; // owns every node ever built
ListNode* build(const std::vector<int>& vals) {
ListNode* head = nullptr;
for (auto it = vals.rbegin(); it != vals.rend(); ++it) {
nodes.push_back(std::make_unique<ListNode>(*it));
nodes.back()->next = head;
head = nodes.back().get();
}
return head;
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(mergeTwoLists(p.build({1, 3, 5}), p.build({2, 4, 6}))) == std::vector<int>{1, 2, 3, 4, 5, 6}));
assert((values(mergeTwoLists(p.build({1, 2, 4}), p.build({1, 3, 4}))) == std::vector<int>{1, 1, 2, 3, 4, 4}));
assert((values(mergeTwoLists(nullptr, p.build({0}))) == std::vector<int>{0}));
assert(mergeTwoLists(nullptr, nullptr) == nullptr);
std::cout << "mergeTwoLists OK\n";
}
function mergeTwoLists(
l1: ListNode<number> | null,
l2: ListNode<number> | null
): ListNode<number> | null {
const dummy = new ListNode(0);
let tail = dummy;
while (l1 !== null && l2 !== null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = l1 ?? l2;
return dummy.next;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode<number> | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(mergeTwoLists(build([1, 3, 5]), build([2, 4, 6])))) === "[1,2,3,4,5,6]", "interleave");
check(JSON.stringify(values(mergeTwoLists(build([1, 2, 4]), build([1, 3, 4])))) === "[1,1,2,3,4,4]", "dupes");
check(JSON.stringify(values(mergeTwoLists(null, build([0])))) === "[0]", "one empty");
check(mergeTwoLists(null, null) === null, "both empty");
console.log("mergeTwoLists OK");
Merging is where lists shine: no auxiliary array, no element copying, just relinking — time and extra space, versus the buffer an array merge needs. Using <= (take from the first list on ties) makes the merge stable, which in turn makes merge sort stable.
Merge K Sorted Lists
Use a min-heap to efficiently merge K sorted lists:
Python:
import heapq
def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
dummy = ListNode(0)
tail = dummy
heap = []
# Initialize heap with the head of each list
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = tail.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Complexity: time where is total nodes and is number of lists. space for the heap.
TIP
See Heaps & Priority Queues for more heap-based techniques.
The tuple (node.val, i, node) carries the list index i as a tie-breaker. Without it, two equal values would make heapq compare the ListNode objects themselves, which raises TypeError because nodes define no ordering. In Java pass a Comparator (PriorityQueue<ListNode>((a, b) -> Integer.compare(a.val, b.val))); in C++ a std::priority_queue with a greater-style lambda over ListNode*.
The alternative with no heap is divide-and-conquer pairing: merge lists 0+1, 2+3, …, then merge the results pairwise, for rounds. Each round touches all nodes once, so it is also , uses extra space (iteratively), and is often faster in practice because merging two lists is a tight loop with no heap operations. Merging the lists one by one into an accumulator, by contrast, is : the accumulator is re-walked times.
Sort a linked list: bottom-up merge sort in O(1) extra space
Sorting a list (LeetCode 148) in with extra space rules out copying to an array and rules out recursion (top-down merge sort uses stack). Bottom-up merge sort does it: for size = 1, 2, 4, …, walk the list cutting off two runs of size nodes, merge them, and append the merged run to the output; stop when one pass produces a single run. Each pass is and there are passes. Quicksort is a poor fit for lists (no random access for pivot selection, and partitioning is no faster than merging), which is why std::list::sort in libstdc++ and Java's Collections.sort (copying to an array, then TimSort) take the routes they do.
The helper split(head, n) cuts the list after n nodes and returns the head of the remainder — the one function where off-by-one bugs live. The implementation:
class ListNode:
__slots__ = ("val", "next")
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def split(head, n):
"""Cut the list after n nodes; return the head of the rest (may be None)."""
for _ in range(n - 1):
if head is None:
return None
head = head.next
if head is None:
return None
rest, head.next = head.next, None
return rest
def merge(a, b, tail):
"""Merge sorted lists a and b after tail; return the new tail."""
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
while tail.next:
tail = tail.next
return tail
def sort_list(head):
n, p = 0, head
while p:
n, p = n + 1, p.next
dummy = ListNode(0, head)
size = 1
while size < n:
tail, cur = dummy, dummy.next
while cur:
left = cur
right = split(left, size)
cur = split(right, size)
tail = merge(left, right, tail)
size *= 2
return dummy.next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert values(sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert values(sort_list(build([]))) == []
assert values(sort_list(build([2, 2, 1]))) == [1, 2, 2]
import random
data = [random.randrange(100) for _ in range(257)]
assert values(sort_list(build(data))) == sorted(data)
print("sort_list OK")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
public class SortList {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode split(ListNode head, int n) { // cut after n nodes, return rest
for (int i = 1; head != null && i < n; i++) head = head.next;
if (head == null) return null;
ListNode rest = head.next;
head.next = null;
return rest;
}
static ListNode merge(ListNode a, ListNode b, ListNode tail) { // returns new tail
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b;
while (tail.next != null) tail = tail.next;
return tail;
}
static ListNode sortList(ListNode head) {
int n = 0;
for (ListNode p = head; p != null; p = p.next) n++;
ListNode dummy = new ListNode(0, head);
for (int size = 1; size < n; size *= 2) {
ListNode tail = dummy, cur = dummy.next;
while (cur != null) {
ListNode left = cur;
ListNode right = split(left, size);
cur = split(right, size);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static int[] values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out.stream().mapToInt(Integer::intValue).toArray();
}
public static void main(String[] args) {
if (!Arrays.equals(values(sortList(build(4, 2, 1, 3))), new int[]{1, 2, 3, 4})) throw new AssertionError();
if (!Arrays.equals(values(sortList(build(-1, 5, 3, 4, 0))), new int[]{-1, 0, 3, 4, 5})) throw new AssertionError();
if (values(sortList(build())).length != 0) throw new AssertionError();
if (!Arrays.equals(values(sortList(build(2, 2, 1))), new int[]{1, 2, 2})) throw new AssertionError();
Random rnd = new Random(7);
int[] data = new int[257];
for (int i = 0; i < data.length; i++) data[i] = rnd.nextInt(100);
int[] want = data.clone();
Arrays.sort(want);
if (!Arrays.equals(values(sortList(build(data))), want)) throw new AssertionError();
System.out.println("sortList OK");
}
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <random>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* split(ListNode* head, int n) { // cut after n nodes, return rest
for (int i = 1; head && i < n; ++i) head = head->next;
if (!head) return nullptr;
ListNode* rest = head->next;
head->next = nullptr;
return rest;
}
ListNode* merge(ListNode* a, ListNode* b, ListNode* tail) { // returns new tail
while (a && b) {
if (a->val <= b->val) { tail->next = a; a = a->next; }
else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b;
while (tail->next) tail = tail->next;
return tail;
}
ListNode* sortList(ListNode* head) {
int n = 0;
for (ListNode* p = head; p; p = p->next) ++n;
ListNode dummy(0);
dummy.next = head;
for (int size = 1; size < n; size *= 2) {
ListNode* tail = &dummy;
ListNode* cur = dummy.next;
while (cur) {
ListNode* left = cur;
ListNode* right = split(left, size);
cur = split(right, size);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
ListNode* head = nullptr;
for (auto it = vals.rbegin(); it != vals.rend(); ++it) {
nodes.push_back(std::make_unique<ListNode>(*it));
nodes.back()->next = head;
head = nodes.back().get();
}
return head;
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(sortList(p.build({4, 2, 1, 3}))) == std::vector<int>{1, 2, 3, 4}));
assert((values(sortList(p.build({-1, 5, 3, 4, 0}))) == std::vector<int>{-1, 0, 3, 4, 5}));
assert(values(sortList(p.build({}))).empty());
assert((values(sortList(p.build({2, 2, 1}))) == std::vector<int>{1, 2, 2}));
std::mt19937 rng(7);
std::vector<int> data(257);
for (int& x : data) x = static_cast<int>(rng() % 100);
std::vector<int> want = data;
std::sort(want.begin(), want.end());
assert(values(sortList(p.build(data))) == want);
std::cout << "sortList OK\n";
}
class ListNode {
val: number;
next: ListNode | null;
constructor(val: number, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function split(head: ListNode | null, n: number): ListNode | null { // cut after n nodes
for (let i = 1; head && i < n; i++) head = head.next;
if (!head) return null;
const rest = head.next;
head.next = null;
return rest;
}
function merge(a: ListNode | null, b: ListNode | null, tail: ListNode): ListNode {
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a ?? b;
while (tail.next) tail = tail.next;
return tail;
}
function sortList(head: ListNode | null): ListNode | null {
let n = 0;
for (let p = head; p; p = p.next) n++;
const dummy = new ListNode(0, head);
for (let size = 1; size < n; size *= 2) {
let tail = dummy;
let cur = dummy.next;
while (cur) {
const left = cur;
const right = split(left, size);
cur = split(right, size);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
function build(vals: number[]): ListNode | null {
let head: ListNode | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(sortList(build([4, 2, 1, 3])))) === "[1,2,3,4]", "basic");
check(JSON.stringify(values(sortList(build([-1, 5, 3, 4, 0])))) === "[-1,0,3,4,5]", "negatives");
check(values(sortList(build([]))).length === 0, "empty");
check(JSON.stringify(values(sortList(build([2, 2, 1])))) === "[1,2,2]", "dupes");
const data = Array.from({ length: 257 }, (_, i) => (i * 37 + 11) % 100);
const want = [...data].sort((x, y) => x - y);
check(JSON.stringify(values(sortList(build(data)))) === JSON.stringify(want), "random");
console.log("sortList OK");
Correctness. After the pass with run size , the list consists of sorted runs of length (the last may be shorter), because each pair of sorted runs of length was merged. Induction from (every single node is a sorted run) to (one run) proves the result sorted. Stability follows from the <= in merge and from always merging a left run with the run immediately to its right.
Pattern 4: Partition
Partition a list around a value — all nodes less than the value come before nodes greater than or equal to it.
def partition(head: ListNode | None, x: int) -> ListNode | None:
less_head = ListNode(0)
greater_head = ListNode(0)
less = less_head
greater = greater_head
current = head
while current:
if current.val < x:
less.next = current
less = less.next
else:
greater.next = current
greater = greater.next
current = current.next
greater.next = None
less.next = greater_head.next
return less_head.next
# --- self-check ---
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(partition(build([1, 4, 3, 2, 5, 2]), 3)) == [1, 2, 2, 4, 3, 5]
assert values(partition(build([2, 1]), 2)) == [1, 2]
assert partition(None, 0) is None
print("partition OK")
import java.util.ArrayList;
import java.util.List;
public class PartitionList {
static class ListNode { int val; ListNode next; ListNode(int v, ListNode n) { val = v; next = n; } }
static ListNode partition(ListNode head, int x) {
ListNode lessHead = new ListNode(0, null), greaterHead = new ListNode(0, null);
ListNode less = lessHead, greater = greaterHead;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (cur.val < x) { less.next = cur; less = cur; }
else { greater.next = cur; greater = cur; }
}
greater.next = null; // terminate: the old next may point back into "less"
less.next = greaterHead.next;
return lessHead.next;
}
static ListNode build(int... vals) {
ListNode head = null;
for (int i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
static List<Integer> values(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
public static void main(String[] args) {
if (!values(partition(build(1, 4, 3, 2, 5, 2), 3)).equals(List.of(1, 2, 2, 4, 3, 5))) throw new AssertionError();
if (!values(partition(build(2, 1), 2)).equals(List.of(1, 2))) throw new AssertionError();
if (partition(null, 0) != null) throw new AssertionError();
System.out.println("partition OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode { int val; ListNode* next = nullptr; explicit ListNode(int v) : val(v) {} };
ListNode* partition(ListNode* head, int x) {
ListNode lessHead(0), greaterHead(0);
ListNode* less = &lessHead;
ListNode* greater = &greaterHead;
for (ListNode* cur = head; cur; cur = cur->next) {
if (cur->val < x) { less->next = cur; less = cur; }
else { greater->next = cur; greater = cur; }
}
greater->next = nullptr;
less->next = greaterHead.next;
return lessHead.next;
}
struct Pool {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* build(const std::vector<int>& vals) {
nodes.clear();
for (int v : vals) nodes.push_back(std::make_unique<ListNode>(v));
for (size_t i = 0; i + 1 < nodes.size(); ++i) nodes[i]->next = nodes[i + 1].get();
return nodes.empty() ? nullptr : nodes[0].get();
}
};
std::vector<int> values(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
int main() {
Pool p;
assert((values(partition(p.build({1, 4, 3, 2, 5, 2}), 3)) == std::vector<int>{1, 2, 2, 4, 3, 5}));
assert((values(partition(p.build({2, 1}), 2)) == std::vector<int>{1, 2}));
assert(partition(nullptr, 0) == nullptr);
std::cout << "partition OK\n";
}
function partition(
head: ListNode<number> | null,
x: number
): ListNode<number> | null {
const lessHead = new ListNode(0);
const greaterHead = new ListNode(0);
let less = lessHead;
let greater = greaterHead;
let current = head;
while (current !== null) {
if (current.val < x) {
less.next = current;
less = less.next;
} else {
greater.next = current;
greater = greater.next;
}
current = current.next;
}
greater.next = null; // terminate the greater list
less.next = greaterHead.next; // connect less → greater
return lessHead.next;
}
// --- self-check ---
class ListNode<T> {
val: T;
next: ListNode<T> | null;
constructor(val: T, next: ListNode<T> | null = null) { this.val = val; this.next = next; }
}
function build(vals: number[]): ListNode<number> | null {
let head: ListNode<number> | null = null;
for (let i = vals.length - 1; i >= 0; i--) head = new ListNode(vals[i], head);
return head;
}
function values(h: ListNode<number> | null): number[] { const out: number[] = []; for (; h; h = h.next) out.push(h.val); return out; }
function check(cond: boolean, msg: string): void { if (!cond) throw new Error(msg); }
check(JSON.stringify(values(partition(build([1, 4, 3, 2, 5, 2]), 3))) === "[1,2,2,4,3,5]", "partition");
check(JSON.stringify(values(partition(build([2, 1]), 2))) === "[1,2]", "two");
check(partition(null, 0) === null, "empty");
console.log("partition OK");
Two dummy heads build two independent lists in one pass, preserving the relative order within each (a stable partition — something the in-place array partition of quicksort does not give you). The greater.next = None line is the one people forget: the last node routed to the "greater" list still carries its original next, which may point to a node in the "less" list, creating a cycle when the two lists are joined. In the test [1, 4, 3, 2, 5, 2] the last node is a 2 in the "less" list, so the bug does not show; with [2, 1] and x = 2, node 2 goes to "greater" with next still pointing at node 1 in "less", and forgetting the line produces the cycle 1 → 2 → 1.
The canonical toolkit in four languages
Everything above in one self-checking program per language: a ListNode, conversion from and to arrays (so tests compare plain arrays), iterative reversal, Floyd's cycle start, merge of two sorted lists, and reversal in groups of k. The same test data runs in all four.
from __future__ import annotations
class ListNode:
__slots__ = ("val", "next")
def __init__(self, val: int = 0, next: ListNode | None = None):
self.val = val
self.next = next
def from_list(vals: list[int]) -> ListNode | None:
dummy = tail = ListNode()
for v in vals:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head: ListNode | None) -> list[int]:
out = []
while head:
out.append(head.val)
head = head.next
return out
def reverse(head: ListNode | None) -> ListNode | None:
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
def cycle_start(head: ListNode | None) -> ListNode | None:
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = head
while slow is not fast:
slow, fast = slow.next, fast.next
return slow
return None
def merge(a: ListNode | None, b: ListNode | None) -> ListNode | None:
dummy = tail = ListNode()
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
def reverse_k_group(head: ListNode | None, k: int) -> ListNode | None:
dummy = ListNode(0, head)
group_prev = dummy
while True:
kth = group_prev # look ahead k nodes
for _ in range(k):
kth = kth.next
if kth is None:
return dummy.next # short final group: leave it
group_next = kth.next
prev, cur = group_next, group_prev.next # reverse exactly k nodes
while cur is not group_next:
cur.next, prev, cur = prev, cur, cur.next
first = group_prev.next # old first is now the group's tail
group_prev.next = kth
group_prev = first
# --- self-check: identical data in all four languages ---
assert to_list(reverse(from_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
assert to_list(reverse(None)) == []
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5, 6]]
for a, b in zip(nodes, nodes[1:]):
a.next = b
nodes[-1].next = nodes[2] # 6 -> 3
assert cycle_start(nodes[0]) is nodes[2]
assert cycle_start(from_list([1, 2, 3])) is None
assert to_list(merge(from_list([1, 3, 5]), from_list([2, 4, 6]))) == [1, 2, 3, 4, 5, 6]
assert to_list(merge(None, from_list([7]))) == [7]
assert to_list(reverse_k_group(from_list([1, 2, 3, 4, 5, 6, 7, 8]), 3)) == [3, 2, 1, 6, 5, 4, 7, 8]
assert to_list(reverse_k_group(from_list([1, 2, 3, 4]), 2)) == [2, 1, 4, 3]
assert to_list(reverse_k_group(from_list([1, 2]), 3)) == [1, 2]
print("linked list toolkit OK")
import java.util.ArrayList;
import java.util.List;
public class LinkedListToolkit {
static final class ListNode {
int val;
ListNode next;
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
static ListNode fromList(int... vals) {
ListNode dummy = new ListNode(0, null), tail = dummy;
for (int v : vals) { tail.next = new ListNode(v, null); tail = tail.next; }
return dummy.next;
}
static List<Integer> toList(ListNode h) {
List<Integer> out = new ArrayList<>();
for (; h != null; h = h.next) out.add(h.val);
return out;
}
static ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; }
return prev;
}
static ListNode cycleStart(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) { slow = slow.next; fast = fast.next; }
return slow;
}
}
return null;
}
static ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0, null), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b;
return dummy.next;
}
static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head), groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k; i++) {
kth = kth.next;
if (kth == null) return dummy.next; // short final group
}
ListNode groupNext = kth.next;
ListNode prev = groupNext, cur = groupPrev.next;
while (cur != groupNext) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; }
ListNode first = groupPrev.next; // becomes the group's tail
groupPrev.next = kth;
groupPrev = first;
}
}
static void expect(List<Integer> got, List<Integer> want) {
if (!got.equals(want)) throw new AssertionError("got " + got + " want " + want);
}
public static void main(String[] args) {
expect(toList(reverse(fromList(1, 2, 3, 4, 5))), List.of(5, 4, 3, 2, 1));
expect(toList(reverse(null)), List.of());
ListNode[] nodes = new ListNode[6];
for (int i = 0; i < 6; i++) nodes[i] = new ListNode(i + 1, null);
for (int i = 0; i < 5; i++) nodes[i].next = nodes[i + 1];
nodes[5].next = nodes[2]; // 6 -> 3
if (cycleStart(nodes[0]) != nodes[2]) throw new AssertionError("cycle start");
if (cycleStart(fromList(1, 2, 3)) != null) throw new AssertionError("no cycle");
expect(toList(merge(fromList(1, 3, 5), fromList(2, 4, 6))), List.of(1, 2, 3, 4, 5, 6));
expect(toList(merge(null, fromList(7))), List.of(7));
expect(toList(reverseKGroup(fromList(1, 2, 3, 4, 5, 6, 7, 8), 3)), List.of(3, 2, 1, 6, 5, 4, 7, 8));
expect(toList(reverseKGroup(fromList(1, 2, 3, 4), 2)), List.of(2, 1, 4, 3));
expect(toList(reverseKGroup(fromList(1, 2), 3)), List.of(1, 2));
System.out.println("linked list toolkit OK");
}
}
#include <cassert>
#include <iostream>
#include <memory>
#include <vector>
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int v, ListNode* n = nullptr) : val(v), next(n) {}
};
// Arena: owns every node so tests can build cycles without leaking.
struct Arena {
std::vector<std::unique_ptr<ListNode>> nodes;
ListNode* make(int v) { nodes.push_back(std::make_unique<ListNode>(v)); return nodes.back().get(); }
ListNode* fromList(const std::vector<int>& vals) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : vals) { tail->next = make(v); tail = tail->next; }
return dummy.next;
}
};
std::vector<int> toList(const ListNode* h) {
std::vector<int> out;
for (; h; h = h->next) out.push_back(h->val);
return out;
}
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
while (head) { ListNode* next = head->next; head->next = prev; prev = head; head = next; }
return prev;
}
ListNode* cycleStart(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = head;
while (slow != fast) { slow = slow->next; fast = fast->next; }
return slow;
}
}
return nullptr;
}
ListNode* merge(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (a && b) {
if (a->val <= b->val) { tail->next = a; a = a->next; } else { tail->next = b; b = b->next; }
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* groupPrev = &dummy;
while (true) {
ListNode* kth = groupPrev;
for (int i = 0; i < k; ++i) {
kth = kth->next;
if (!kth) return dummy.next; // short final group
}
ListNode* groupNext = kth->next;
ListNode* prev = groupNext;
ListNode* cur = groupPrev->next;
while (cur != groupNext) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; }
ListNode* first = groupPrev->next; // becomes the group's tail
groupPrev->next = kth;
groupPrev = first;
}
}
int main() {
Arena A;
assert((toList(reverse(A.fromList({1, 2, 3, 4, 5}))) == std::vector<int>{5, 4, 3, 2, 1}));
assert(toList(reverse(nullptr)).empty());
std::vector<ListNode*> nodes;
for (int v = 1; v <= 6; ++v) nodes.push_back(A.make(v));
for (int i = 0; i < 5; ++i) nodes[i]->next = nodes[i + 1];
nodes[5]->next = nodes[2]; // 6 -> 3
assert(cycleStart(nodes[0]) == nodes[2]);
assert(cycleStart(A.fromList({1, 2, 3})) == nullptr);
assert((toList(merge(A.fromList({1, 3, 5}), A.fromList({2, 4, 6}))) == std::vector<int>{1, 2, 3, 4, 5, 6}));
assert((toList(merge(nullptr, A.fromList({7}))) == std::vector<int>{7}));
assert((toList(reverseKGroup(A.fromList({1, 2, 3, 4, 5, 6, 7, 8}), 3)) == std::vector<int>{3, 2, 1, 6, 5, 4, 7, 8}));
assert((toList(reverseKGroup(A.fromList({1, 2, 3, 4}), 2)) == std::vector<int>{2, 1, 4, 3}));
assert((toList(reverseKGroup(A.fromList({1, 2}), 3)) == std::vector<int>{1, 2}));
std::cout << "linked list toolkit OK\n";
}
class ListNode {
val: number;
next: ListNode | null;
constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}
function fromList(vals: number[]): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
for (const v of vals) { tail.next = new ListNode(v); tail = tail.next; }
return dummy.next;
}
function toList(h: ListNode | null): number[] {
const out: number[] = [];
for (; h; h = h.next) out.push(h.val);
return out;
}
function reverse(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
while (head) { const next: ListNode | null = head.next; head.next = prev; prev = head; head = next; }
return prev;
}
function cycleStart(head: ListNode | null): ListNode | null {
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
if (slow === fast) {
slow = head;
while (slow !== fast) { slow = slow!.next; fast = fast!.next; }
return slow;
}
}
return null;
}
function merge(a: ListNode | null, b: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
while (a && b) {
if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a ?? b;
return dummy.next;
}
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
const dummy = new ListNode(0, head);
let groupPrev = dummy;
while (true) {
let kth: ListNode | null = groupPrev;
for (let i = 0; i < k; i++) {
kth = kth!.next;
if (!kth) return dummy.next; // short final group
}
const groupNext: ListNode | null = kth!.next;
let prev: ListNode | null = groupNext;
let cur: ListNode | null = groupPrev.next;
while (cur !== groupNext) { const next: ListNode | null = cur!.next; cur!.next = prev; prev = cur; cur = next; }
const first = groupPrev.next!; // becomes the group's tail
groupPrev.next = kth;
groupPrev = first;
}
}
function expect(got: number[], want: number[]): void {
if (JSON.stringify(got) !== JSON.stringify(want)) throw new Error(`got ${got} want ${want}`);
}
expect(toList(reverse(fromList([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]);
expect(toList(reverse(null)), []);
const nodes = [1, 2, 3, 4, 5, 6].map(v => new ListNode(v));
for (let i = 0; i < 5; i++) nodes[i].next = nodes[i + 1];
nodes[5].next = nodes[2]; // 6 -> 3
if (cycleStart(nodes[0]) !== nodes[2]) throw new Error("cycle start");
if (cycleStart(fromList([1, 2, 3])) !== null) throw new Error("no cycle");
expect(toList(merge(fromList([1, 3, 5]), fromList([2, 4, 6]))), [1, 2, 3, 4, 5, 6]);
expect(toList(merge(null, fromList([7]))), [7]);
expect(toList(reverseKGroup(fromList([1, 2, 3, 4, 5, 6, 7, 8]), 3)), [3, 2, 1, 6, 5, 4, 7, 8]);
expect(toList(reverseKGroup(fromList([1, 2, 3, 4]), 2)), [2, 1, 4, 3]);
expect(toList(reverseKGroup(fromList([1, 2]), 3)), [1, 2]);
console.log("linked list toolkit OK");
In reverse_k_group the reversal loop starts with prev = group_next instead of None. That single choice stitches the reversed group's new tail (its old first node) directly to the next group, so only one more link — group_prev.next = kth — is needed to attach the group's new head. Compare this with the k-group bugs listed under Pitfalls.
More classic patterns
Two-pass vs one-pass: remove the nth node from the end
The two-pass solution counts the length , then walks steps to the predecessor of the target. It is and perfectly acceptable. The one-pass version keeps a gap: advance fast steps from a dummy, then move fast and slow together until fast is null; slow is then the predecessor of the node to delete. The dummy handles (delete the head). Both make about pointer moves; "one pass" does not mean less work, it means you never need the length — which matters when the list is a stream you can only walk once with two cursors.
Trace on 1 → 2 → 3 → 4 → 5, n = 2. Both pointers start at the dummy; fast first advances steps:
| step | fast | slow |
|---|---|---|
| 0 | 3 (dummy + 3 steps) | dummy |
| 1 | 4 | 1 |
| 2 | 5 | 2 |
| 3 | null | 3 |
slow stops on node 3, so slow.next is node 4 — the 2nd from the end — and the result is 1 → 2 → 3 → 5, matching the Try It Yourself answer below. Invariant: throughout the second loop, fast is exactly nodes ahead of slow, so when fast falls off the end (position counting the dummy as 0), slow is at position , the predecessor of the target.
The classic off-by-one is to count the steps from the head instead of the dummy while still starting slow at the dummy. fast then begins on node 4 and slow stops on node 2, deleting node 3 instead of node 4. (The Try It Yourself version is a consistent variant: slow and fast both start at the head, the gap is , and the loop stops when fast.next is null — it simply cannot delete the head without a special case.) Trace a five-node example by hand before submitting.
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def remove_nth_from_end(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 # slow is the predecessor of the target
return dummy.next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(remove_nth_from_end(build([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
assert values(remove_nth_from_end(build([1, 2, 3, 4, 5]), 5)) == [2, 3, 4, 5] # head removed
assert values(remove_nth_from_end(build([1]), 1)) == []
print("remove_nth_from_end OK")
Intersection of two lists (length-alignment proof)
Two singly linked lists may merge into a shared tail (a "Y" shape). Find the first shared node in time and space.
Length alignment. Compute lengths and ; advance the longer list's pointer by ; then step both together, comparing node identity, until they are equal (the intersection) or both null (no intersection). Proof: if the lists share a tail of length , list A is nodes and list B is nodes, where and are the private prefixes. After skipping nodes on the longer list, both pointers are exactly nodes from the end, so they are the same distance from the first shared node and arrive at it on the same step. They cannot meet earlier, because before that step at least one pointer is in its private prefix, and private nodes are distinct. If there is no shared tail () both reach null together.
Trace for A = a1, a2, c1, c2, c3 and B = b1, b2, b3, c1, c2, c3 (lengths 5 and 6, so B's pointer skips one node):
| step | pA | pB | same node? |
|---|---|---|---|
| 0 | a1 | b2 | no |
| 1 | a2 | b3 | no |
| 2 | c1 | c1 | yes |
Pointer switching is the same proof without computing lengths: walk pA through A then B, and pB through B then A. Both travel nodes before reaching the shared node the second time around, so they meet there (or both hit null after steps when ).
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def get_intersection(a, b):
pa, pb = a, b
while pa is not pb:
pa = pa.next if pa else b # switch to the other list at the end
pb = pb.next if pb else a
return pa # shared node, or None
shared = ListNode(8, ListNode(4, ListNode(5)))
A = ListNode(4, ListNode(1, shared))
B = ListNode(5, ListNode(6, ListNode(1, shared)))
assert get_intersection(A, B) is shared
assert get_intersection(ListNode(1), ListNode(1)) is None # equal values, different nodes
print("get_intersection OK")
The second assertion is the point of the problem: two nodes with value 1 are not the same node. Compare with is / == on references, never with .val.
Palindrome linked list
Decide whether a list reads the same both ways in time and space: find the middle with fast/slow, reverse the second half in place, compare the halves node by node, then reverse the second half back so the caller's list is unchanged. Restoring the input is what separates a production answer from a puzzle answer; interviewers notice.
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
def is_palindrome(head) -> bool:
if head is None or head.next is None:
return True
slow, fast = head, head.next # left-middle: first half never shorter
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second = reverse(slow.next)
p, q, ok = head, second, True
while q: # second half is the shorter (or equal) one
if p.val != q.val:
ok = False
break
p, q = p.next, q.next
slow.next = reverse(second) # restore the original list
return ok
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
for vals, want in [([1, 2, 2, 1], True), ([1, 2, 3, 2, 1], True), ([1, 2], False), ([1], True), ([1, 2, 3], False)]:
h = build(vals)
assert is_palindrome(h) == want, vals
assert values(h) == vals, "input must be restored"
print("is_palindrome OK")
Add two numbers
Digits stored least-significant first make addition a single synchronised walk with a carry: digit (x + y + carry) % 10, new carry (x + y + carry) // 10, and keep going while either list or the carry remains. Trace for 342 + 465 (lists 2→4→3 and 5→6→4):
| i | digit a | digit b | carry in | sum | digit out | carry out |
|---|---|---|---|---|---|---|
| 0 | 2 | 5 | 0 | 7 | 7 | 0 |
| 1 | 4 | 6 | 0 | 10 | 0 | 1 |
| 2 | 3 | 4 | 1 | 8 | 8 | 0 |
Result 7→0→8 (807). The case that breaks naive loops is a final carry: 999 + 1 gives 0→0→0→1, one node longer than either input.
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def add_two_numbers(a, b):
dummy = tail = ListNode()
carry = 0
while a or b or carry: # the carry keeps the loop alive
s = carry + (a.val if a else 0) + (b.val if b else 0)
carry, digit = divmod(s, 10)
tail.next = ListNode(digit)
tail = tail.next
a = a.next if a else None
b = b.next if b else None
return dummy.next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
assert values(add_two_numbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8]
assert values(add_two_numbers(build([9, 9, 9]), build([1]))) == [0, 0, 0, 1]
assert values(add_two_numbers(build([0]), build([0]))) == [0]
print("add_two_numbers OK")
When digits are stored most-significant first (LeetCode 445), either reverse both inputs, or push digits onto two stacks and build the result by prepending.
Copy a list with random pointers: the interleaving trick
Each node has next and a random pointer to any node or null; produce a deep copy. The straightforward solution maps each original node to its copy in a hash map (two passes, space). The interleaving trick gets extra space by using the list itself as the map:
- Weave: after each original node
X, insert its copyX':A → A' → B → B' → …. Now "the copy ofX" is simplyX.next. - Random: for each original
X, setX'.random = X.random.nextifX.randomexists (the copy of the target is right after the target). - Unweave: restore
X.next = X'.nextand setX'.next = X'.next.next(orNone), splitting the two lists apart.
class Node:
def __init__(self, val, next=None, random=None):
self.val, self.next, self.random = val, next, random
def copy_random_list(head):
if head is None:
return None
p = head # 1. weave copies in
while p:
p.next = Node(p.val, p.next)
p = p.next.next
p = head # 2. set random pointers on copies
while p:
if p.random:
p.next.random = p.random.next
p = p.next.next
p, new_head = head, head.next # 3. unweave
while p:
copy = p.next
p.next = copy.next
copy.next = copy.next.next if copy.next else None
p = p.next
return new_head
# 7 -> 13 -> 11 -> 10 -> 1, randoms: 13->7, 11->1, 10->11, 1->7
n = [Node(v) for v in [7, 13, 11, 10, 1]]
for a, b in zip(n, n[1:]):
a.next = b
n[1].random, n[2].random, n[3].random, n[4].random = n[0], n[4], n[2], n[0]
c = copy_random_list(n[0])
seen_orig = set(map(id, n))
out, p = [], c
while p:
assert id(p) not in seen_orig # deep copy: no shared nodes
out.append((p.val, p.random.val if p.random else None))
p = p.next
assert out == [(7, None), (13, 7), (11, 1), (10, 11), (1, 7)]
p, i = n[0], 0 # the original is intact
while p:
assert p is n[i]
p, i = p.next, i + 1
print("copy_random_list OK")
Reorder list: three patterns in one
LeetCode 143 asks for in place. It is find-middle, reverse-second-half and merge-alternately back to back — a good self-test that you can compose the primitives without losing a pointer. The solution is in the practice ladder.
Advanced: LRU Cache
An LRU (Least Recently Used) cache combines a doubly linked list with a hash map. This is one of the most frequently asked interview questions at top companies.
Python:
class DLLNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache: dict[int, DLLNode] = {}
# Sentinel nodes avoid null checks
self.head = DLLNode() # most recently used
self.tail = DLLNode() # least recently used
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node: DLLNode) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _add_to_front(self, node: DLLNode) -> None:
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add_to_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = DLLNode(key, value)
self.cache[key] = node
self._add_to_front(node)
if len(self.cache) > self.capacity:
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
Complexity: for both get and put.
Why each node stores its key as well as its value: when the tail node is evicted, the cache must also delete it from the hash map, and the only way to find its map entry is by key. Why doubly linked: _remove must reach the node's predecessor in . Why two sentinels: _remove and _add_to_front then contain no branches at all. In production you rarely write this by hand — Java's LinkedHashMap with accessOrder = true and an overridden removeEldestEntry is an LRU cache, and Python's OrderedDict.move_to_end plus popitem(last=False) (or functools.lru_cache) does the same — but every one of those is exactly this structure inside. The module capstone, Build an LRU Cache & Benchmark It, builds it in all four languages, measures it, and compares it against the library versions; the policy side (LRU vs LFU vs ARC) is in Caching Strategies.
XOR linked lists and unrolled linked lists
Two variations trade the textbook node shape for memory or cache efficiency.
XOR linked list. Store a single field link = addr(prev) XOR addr(next) instead of two pointers. Walking forward from a node, you know the address of the node you came from, so next = link XOR prev; walking backward is symmetric. You get a doubly linked list for the memory of a singly linked one (Prasad Sinha's 2004 Linux Journal article "A Memory-Efficient Doubly Linked List" popularised it; the trick is much older). The costs: you cannot start a traversal from an arbitrary node without knowing a neighbour, deletion given only a node pointer is impossible, and debuggers show garbage. And it cannot work in garbage-collected languages at all: a tracing collector finds live objects by following pointers it can see, and an XOR-ed value is not a pointer. The collector would consider the neighbours unreachable and free them — or a moving collector would relocate them without updating the XOR-ed field. Java, Python, JavaScript and Go give you no portable way to get or use a raw address; even in C and C++, converting pointers to uintptr_t and back is implementation-defined (it works on every mainstream platform, but conservative leak checkers and garbage collectors such as Boehm GC lose track of the objects). Today, with 64-bit memory cheap, it is a curiosity — worth knowing as an interview question, rarely worth shipping.
Unrolled linked list. Each node holds a small array of elements (a block) plus next/prev. Iteration within a block is a contiguous scan, so cache misses drop by a factor of the block size, and the per-element pointer overhead is amortised over the block. Insertion into a full block splits it; deletion that leaves a block under-full merges with a neighbour — the same balancing idea as a B-tree leaf level. Real uses:
- CPython's
collections.dequeis a doubly linked list of fixed-size blocks of 64 slots (BLOCKLENinModules/_collectionsmodule.c). Appends and pops at both ends are and touch one block; indexing into the middle is block hops. This is whydeque[i]is legal but slow, and whydequebeatslistfor queue workloads (list.pop(0)is ). See Queues, Deques & Circular Buffers. - Redis lists are a quicklist: a doubly linked list whose nodes are compact listpacks (ziplists before Redis 7), so
LPUSH/RPOPstay while memory stays dense. See Redis Internals. - Text editors' rope and piece-table cousins and C++'s
std::deque(a map of fixed-size blocks rather than a linked list, but the same "array of chunks" idea) apply the same compromise.
Skip lists go the other direction: they add more pointers — each node gets a random number of forward links at increasing levels — so that search can skip ahead and runs in expected , like a balanced tree but with only local, lock-friendly updates. William Pugh introduced them in 1990. Redis sorted sets, LevelDB/RocksDB memtables and Java's ConcurrentSkipListMap use them. They are covered in Advanced Data Structures.
Common Edge Cases
Always Handle These
- Null head: The list is empty
- Single node: Head is also the tail
- Two nodes: Tests pointer manipulation boundaries
- Cycle: Operations that traverse to the end will infinite-loop
- Modifying the head: Use a dummy node to avoid special cases
Pitfalls
- Losing the head (or the rest of the list). Overwriting
node.nextbefore saving it orphans everything after it — in a GC language the nodes silently vanish, in C++ they leak. Rule: savenextfirst, then rewire. Keep a dummy so the head is always reachable asdummy.next. - Null dereferences in fast/slow loops. The guard must be
fast and fast.next(both), checked beforefast.next.next. In reverse-between,prev.next!andcurrent.next!assume1 ≤ left ≤ right ≤ length; validate input if it is not guaranteed. - Accidental cycles when relinking. Forgetting
head.next = Nonein recursive reversal, orgreater.next = Nonein partition, or not terminating the last run in merge sort, leaves an oldnextpointing backwards. Symptoms: an infinite loop in the next function that walks the list, far from the bug. Debug by running Floyd on your output. - Off-by-one in k-groups. Reversing a short final group when the problem says to keep it (count ahead first); counting
kfrom the wrong starting node (fromgroup_prev, stepktimes to land on the k-th node); and forgetting to movegroup_prevto the old first node of the reversed group, which makes the next group attach in the wrong place. - Off-by-one in gaps. Remove-nth-from-end with the gap measured from the head instead of the dummy (see the deliberate wrong trace above). Middle-of-list returning the right-middle when the algorithm (merge sort, palindrome) needs the left-middle.
- Modifying while iterating. Advancing with
cur = cur.nextafter you have relinked or freedcurfollows the new (wrong) pointer, or a freed one. Savenextbefore the body. In Java, structurally modifying aLinkedListwhile iterating with a for-each loop throwsConcurrentModificationException; useIterator.remove(). - Value equality instead of identity. Cycle detection and intersection compare nodes, not values:
slow is fastin Python,==on references in Java, pointer comparison in C++. Lists with repeated values break value-based comparisons. - Recursion depth on long lists. Python's default limit is 1000 frames; Java overflowed between 10,000 and 20,000 frames in our test; C++ crashes without a message. This also bites C++ destructors: a
unique_ptrchain destroys recursively, so a list of a few hundred thousand nodes can overflow the stack when it goes out of scope. Write an iterative destructor (while (head) head = std::move(head->next);). - Heap tie-breaking in merge-k. Pushing
(val, node)into Python'sheapqraisesTypeErroron equal values; include an index. - Forgetting the final carry in add-two-numbers, and forgetting to restore the input in palindrome checks.
- Using a linked list for random access.
LinkedList.get(i)in Java is ; a loopfor (i = 0; i < list.size(); i++) list.get(i)is . Use an iterator, or anArrayList.
Linked List vs Array
| Criterion | Linked List | Array |
|---|---|---|
| Random access | ||
| Insert/delete at known position | ||
| Cache performance | Poor (scattered memory) | Excellent (contiguous) |
| Memory overhead | Extra pointer per node | None |
| Size flexibility | Dynamic | Fixed (or amortized resizing) |
Production Reality
In production, arrays almost always beat linked lists due to cache locality. Modern CPUs are optimized for sequential memory access. Linked lists scatter nodes across the heap, causing cache misses on every pointer dereference. Use linked lists when you need frequent insertions/deletions at arbitrary positions (e.g., LRU cache) or when you're implementing other data structures (e.g., hash table chaining, adjacency lists).
A refinement of the warning: "frequent insertions at arbitrary positions" helps a list only if you already hold the node at that position. If you must first search for the position, the search is pointer chasing and the array — which pays for the shift but does it with a fast memmove — usually still wins, as Stroustrup's benchmark shows.
Real-world uses
- Memory allocators. Free lists thread unused blocks through themselves; segregated free lists keep one list per size class; slab allocators keep per-slab free lists of objects. See Memory Allocators.
- Operating system kernels. Linux's intrusive
list_head(include/linux/list.h) links tasks, timers, inodes, modules and device structures;hlist_headis a singly linked variant with a one-pointer head used for hash-table buckets, halving bucket memory. The kernel's RCU-protected list variants let readers walk a list with no locks while writers splice. Wait queues and the scheduler's per-CPU structures also lean on it; see CPU Scheduling and OS Algorithms. - LRU caches. Every LRU implementation —
LinkedHashMap,OrderedDict, memcached's per-slab-class LRU, the buffer pool of a database — is a doubly linked list plus an index. The capstone builds one: LRU Cache capstone. - Hash table chaining. Java's
HashMapbuckets are linked lists until they treeify; C++std::unordered_map(libstdc++) keeps all nodes in one singly linked list with buckets pointing into it. See Hash Tables. - Undo/redo and history. Editors, browsers' back/forward history and command-pattern undo stacks are lists (often doubly linked) of states or operations; persistent lists make "keep every version" cheap by sharing tails.
- Lock-free structures. Michael–Scott queues and Harris's lock-free linked list underpin concurrent queues and sets in Java's
java.util.concurrentand in C++ libraries; see Lock-Free Programming. - Graph adjacency lists and sparse matrices (one list of non-zeros per row) in Graphs.
- Blockchains and append-only logs link each block to its predecessor by hash — a linked list whose "pointer" is a cryptographic digest, giving tamper evidence (Hashing Algorithms).
- Language runtimes. Lisp, Scheme, Haskell, Erlang and OCaml lists are singly linked cons cells; garbage collectors keep object lists and free lists; Python's cyclic GC links tracked containers into generation lists.
Variations
- Doubly linked with sentinel(s) — delete of a held node; the LRU workhorse.
- Circular — round-robin scheduling, ring of players (Josephus problem), Linux
list_head. - Intrusive — links embedded in the payload; no allocation per link; one object on many lists.
- XOR linked list — doubly linked in one pointer's space; manual-memory languages only.
- Unrolled — arrays in nodes; CPython
deque, Redis quicklist. - Skip list — layered express lanes for expected search (Advanced Data Structures).
- Persistent / immutable list — structural sharing of tails; functional languages.
- Self-organising list — move-to-front or transpose on access; the theory behind LRU and an early adaptive-compression trick (move-to-front coding in bzip2).
- Multi-level / flattened lists — child pointers to sublists (LeetCode 430), the shape of nested document structures.
- Implicit linked list in an array —
i → nums[i], used by Floyd's find-the-duplicate in Arrays & Strings; also free lists stored as indices in an array pool, common in game engines and embedded code where allocation is forbidden.
Practice Problems
| Problem | Pattern | Difficulty |
|---|---|---|
| Reverse Linked List | Reversal | Easy |
| Linked List Cycle | Fast/slow pointer | Easy |
| Merge Two Sorted Lists | Merge | Easy |
| Remove Nth Node From End | Two pointers (gap) | Medium |
| Reorder List | Find middle + reverse + merge | Medium |
| Add Two Numbers | Carry propagation | Medium |
| Copy List with Random Pointer | Hash map clone | Medium |
| LRU Cache | Doubly linked list + hash map | Medium |
| Reverse Nodes in k-Group | Sub-list reversal | Hard |
| Merge K Sorted Lists | Heap + merge | Hard |
Practice ladder
Fifteen problems from warm-up to hard, each described in our own words. Follow the link for the official statement and judge.
1. Reverse Linked List (LeetCode 206) — Reverse a singly linked list. Teaches the prev / current / next invariant; do it iteratively and recursively.
Hint
Save next before overwriting current.next. The answer is prev when current becomes null.
2. Merge Two Sorted Lists (LeetCode 21) — Splice two sorted lists into one. Teaches the dummy head and tail pointer.
Hint
Dummy node, tail pointer, attach the smaller head, and at the end attach whichever list is non-empty.
3. Linked List Cycle (LeetCode 141) — Does the list loop? Teaches Floyd's phase 1 and the double null check.
Hint
while fast and fast.next. Compare nodes by identity.
4. Middle of the Linked List (LeetCode 876) — Return the middle node (the second middle for even lengths). Teaches fast/slow for splitting.
Hint
Both pointers start at the head; slow is the right-middle when fast cannot move two more steps.
5. Remove Nth Node From End of List (LeetCode 19) — Delete the n-th node from the end in one pass. Teaches the gap technique and why the dummy is needed.
Hint
Gap of n + 1 measured from a dummy, so slow stops on the predecessor. Test n equal to the length.
6. Intersection of Two Linked Lists (LeetCode 160) — First node shared by two lists. Teaches the length-alignment proof and node identity.
Hint
Either align lengths or switch heads at the end; both pointers then travel the same total distance.
7. Palindrome Linked List (LeetCode 234) — Is the list a palindrome, in space? Teaches middle + reverse + compare + restore.
Hint
Find the left-middle, reverse what follows it, compare, reverse back.
Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def is_palindrome(head):
def rev(h):
prev = None
while h:
h.next, prev, h = prev, h, h.next
return prev
if not head or not head.next:
return True
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second = rev(slow.next)
p, q, ok = head, second, True
while q:
if p.val != q.val:
ok = False
break
p, q = p.next, q.next
slow.next = rev(second)
return ok
h = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
assert is_palindrome(h) and not is_palindrome(ListNode(1, ListNode(2)))
print("ok")
time, extra space, and the input is restored.
8. Add Two Numbers (LeetCode 2) — Sum two numbers stored as reversed digit lists. Teaches carry propagation and the final-carry node.
Hint
Loop while a or b or carry.
9. Linked List Cycle II (LeetCode 142) — Return the node where the cycle begins. Teaches Floyd's phase 2 and its proof.
Hint
After the meeting, one pointer to the head, both at speed one. Be ready to explain .
10. Reverse Linked List II (LeetCode 92) — Reverse positions left..right in one pass. Teaches head-insertion reversal with a fixed prev.
Hint
Walk prev to position left − 1 from a dummy; then move the node after current to just after prev, right − left times.
11. Reorder List (LeetCode 143) — Interleave the first half with the reversed second half, in place. Teaches composing three primitives.
Hint
Middle (left-middle), cut, reverse the second half, merge alternately.
Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def reorder_list(head) -> None:
if not head or not head.next:
return
slow, fast = head, head.next
while fast and fast.next:
slow, fast = slow.next, fast.next.next
second, slow.next = slow.next, None # cut after the left-middle
prev = None
while second: # reverse the second half
second.next, prev, second = prev, second, second.next
first, second = head, prev
while second: # merge alternately
n1, n2 = first.next, second.next
first.next, second.next = second, n1
first, second = n1, n2
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
def values(h):
out = []
while h:
out.append(h.val)
h = h.next
return out
h = build([1, 2, 3, 4, 5]); reorder_list(h); assert values(h) == [1, 5, 2, 4, 3]
h = build([1, 2, 3, 4]); reorder_list(h); assert values(h) == [1, 4, 2, 3]
print("ok")
time, space.
12. Copy List with Random Pointer (LeetCode 138) — Deep-copy a list whose nodes also point to arbitrary nodes. Teaches the hash-map clone, then the interleaving trick.
Hint
Weave copies after originals so that copy(X) == X.next; set randoms; unweave.
13. Sort List (LeetCode 148) — Sort in ; the follow-up asks for extra space. Teaches bottom-up merge sort and the split helper.
Hint
Passes with run size 1, 2, 4, …; each pass cuts two runs, merges them, and appends to a tail.
14. Merge k Sorted Lists (LeetCode 23) — Merge k sorted lists. Teaches heap-based merging and divide-and-conquer pairing.
Hint
Heap of (val, index, node), or merge lists pairwise in rounds.
Solution
import heapq
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
def merge_k_lists(lists):
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
def build(vals):
head = None
for v in reversed(vals):
head = ListNode(v, head)
return head
out, p = [], merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6]), None])
while p:
out.append(p.val)
p = p.next
assert out == [1, 1, 2, 3, 4, 4, 5, 6]
print("ok")
time, heap space. Note tail.next = tail = node assigns left to right in Python: first tail.next, then tail.
15. Reverse Nodes in k-Group (LeetCode 25) — Reverse every block of k nodes; leave a short tail alone. Teaches look-ahead, bounded reversal and stitching.
Hint
Count k nodes ahead from group_prev; if you run out, stop. Reverse with prev = group_next so the tail is stitched automatically, then move group_prev to the old first node.
Beyond the ladder. LRU Cache (LeetCode 146) — the design problem the module capstone expands; Rotate List (LeetCode 61) — close the list into a ring, then cut it at n − k mod n; Partition List (LeetCode 86) — the two-dummy stable partition from this page; and Find the Duplicate Number (LeetCode 287) — Floyd on an implicit list.
Interview follow-ups
- "Detect the cycle without modifying the list and without extra memory." Floyd (or Brent). Marking visited nodes or a hash set of seen nodes are the -space answers to mention first.
- "Why must the pointers meet? Couldn't fast jump over slow?" Inside the cycle the gap shrinks by exactly one per step, so it passes through zero; fast cannot skip. With speeds 1 and 3 the gap shrinks by 2 and could skip on even cycle lengths before eventually meeting — another reason 1 and 2 are the canonical choice.
- "How long is the cycle?" From the meeting point walk until you return, counting steps; or use Brent, which reports it directly.
- "Reverse recursively — what is the space cost and when does it fail?" stack; Python fails at about 1000 nodes by default, Java in the low tens of thousands.
- "Delete a node given only a pointer to it." Copy the next node's value and unlink the next node; impossible for the tail; breaks outside references to the next node.
- "Sort a linked list in O(1) extra space." Bottom-up merge sort. Why not quicksort: no random access for pivots and no cache benefit; merge is natural on lists.
- "Merge k lists — compare heap vs pairwise merging." Both ; pairwise needs no heap and extra space iteratively; heap is better when the lists arrive as streams.
- "Why does LRU use a doubly linked list rather than singly?" Removal of an arbitrary node needs its predecessor in . Could you use a singly linked list by storing the predecessor in the map? Yes, but every splice must update the map entry of the following node too — doable, error-prone.
- "Is a linked list ever faster than an array in practice?" When you hold node pointers and splice often (LRU), when addresses must stay stable, when an element must be on several lists (intrusive), or for lock-free stacks/queues. For scanning and indexing, almost never.
- "Make the LRU cache thread-safe." A single lock around both map and list is the baseline; sharded caches split the key space; production caches often approximate LRU (CLOCK, sampled LRU in Redis) to avoid the global list lock — see Caching Strategies.
Further Reading
- Arrays & Strings — the contiguous counterpart
- Heaps & Priority Queues — for merge K lists
- Hash Tables — combined with linked lists for chaining and LRU caches
- How Data Structures Live in Memory — cache lines and pointer chasing
- Capstone: Build an LRU Cache & Benchmark It
- Advanced Data Structures — skip lists and beyond
- Memory Allocators — free lists in production
- Donald Knuth, The Art of Computer Programming, Vol. 1, §2.2.3–2.2.5 (linked allocation, circular and doubly linked lists) and Vol. 2, §3.1 exercise 6 (cycle detection, credited to Floyd)
- Richard P. Brent, "An improved Monte Carlo factorization algorithm", BIT Numerical Mathematics 20 (1980) 176–184
- CLRS, Introduction to Algorithms, 4th ed., §10.2 (linked lists, sentinels)
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., §1.3 (bags, queues and stacks with linked lists)
- William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", CACM 33(6), 1990
- Linux kernel source,
include/linux/list.h; CPython source,Modules/_collectionsmodule.c(deque blocks)
Try It Yourself
Problem 1: Given the linked list 1 -> 2 -> 3 -> 4 -> 5, reverse it to produce 5 -> 4 -> 3 -> 2 -> 1.
Solution
Use three pointers: prev, current, next.
- Initialize
prev = null,current = 1 - Step 1: save
next = 2, point1.next = null, advanceprev = 1,current = 2 - Step 2: save
next = 3, point2.next = 1, advanceprev = 2,current = 3 - Continue until
current = null. Returnprevwhich is node 5. Time: , Space: .
Problem 2: Detect if the linked list 1 -> 2 -> 3 -> 4 -> 5 -> 3 (where 5 points back to 3) has a cycle, and find where the cycle starts.
Solution
Use Floyd's algorithm (fast and slow pointers):
- Phase 1: slow moves 1 step, fast moves 2 steps. They meet inside the cycle.
- Phase 2: Reset slow to head. Move both slow and fast 1 step at a time. They meet at the cycle start. The cycle starts at node 3.
Problem 3: Find the middle node of 1 -> 2 -> 3 -> 4 -> 5.
Solution
Use fast and slow pointers. Slow moves 1 step, fast moves 2 steps.
- Start: slow=1, fast=1
- Step 1: slow=2, fast=3
- Step 2: slow=3, fast=5
fast.nextis null, stop. Middle node is 3.
Problem 4: Merge two sorted lists: 1 -> 3 -> 5 and 2 -> 4 -> 6 into one sorted list.
Solution
Use a dummy head and compare nodes from both lists:
- Compare 1 vs 2: take 1, advance list 1
- Compare 3 vs 2: take 2, advance list 2
- Compare 3 vs 4: take 3, advance list 1
- Compare 5 vs 4: take 4, advance list 2
- Compare 5 vs 6: take 5, advance list 1
- Append remaining: 6
Result:
1 -> 2 -> 3 -> 4 -> 5 -> 6. Time: .
Problem 5: Remove the 2nd node from the end of 1 -> 2 -> 3 -> 4 -> 5.
Solution
Use two pointers with a gap of 2:
- Advance
fast2 steps: fast=3 - Move both together: slow=1,fast=3 → slow=2,fast=4 → slow=3,fast=5
fast.nextis null, soslow.nextis the node to remove (node 4)- Set
slow.next = slow.next.nextResult:1 -> 2 -> 3 -> 5.
Problem 6: In the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3 (6 links back to 3), at which node do Floyd's pointers first meet, and how many steps does phase 2 take?
Solution
, . They meet at node 5 after 4 steps (slow 4, fast 8, difference one lap). The meeting offset is , and phase 2 takes steps: 1→2→3 for the head pointer and 5→6→3 for the other.
Problem 7: Reverse 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 in groups of 3.
Solution
Groups [1,2,3] and [4,5,6] are full and get reversed; [7] is short and stays. Result: 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7.
Quick Quiz
1. What is the time complexity of accessing the -th element in a singly linked list?
- a)
- b)
- c)
- d)
Answer
c) — Linked lists do not support random access. You must traverse from the head, taking up to steps in the worst case.
2. Why is the "dummy head" technique useful in linked list problems?
- a) It makes the list doubly linked
- b) It eliminates special-case handling when the head might be modified
- c) It reduces time complexity
- d) It prevents memory leaks
Answer
b) It eliminates special-case handling when the head might be modified — Operations like deletion or insertion at the head require special logic without a dummy node. The dummy node ensures there is always a node before the first real element.
3. In Floyd's cycle detection algorithm, what happens if there is no cycle?
- a) The slow pointer reaches null
- b) The fast pointer reaches null (or
fast.nextis null) - c) Both pointers reach null simultaneously
- d) The algorithm runs forever
Answer
b) The fast pointer reaches null (or fast.next is null) — The fast pointer moves ahead of slow and will reach the end of the list first if there is no cycle.
4. What is the time complexity of merging K sorted linked lists using a min-heap?
- a)
- b)
- c)
- d)
Answer
b) — where is the total number of nodes and is the number of lists. Each of the nodes is pushed and popped from a heap of size , each operation taking .
5. Why do linked lists generally perform worse than arrays in practice despite having insertion?
- a) They use more memory
- b) Poor cache locality -- nodes are scattered across memory causing cache misses
- c) They cannot store large elements
- d) They require garbage collection
Answer
b) Poor cache locality -- nodes are scattered across memory causing cache misses — Arrays store elements contiguously in memory, which modern CPUs can prefetch efficiently. Linked list nodes are scattered on the heap, causing a cache miss on almost every pointer dereference.
6. In phase 2 of Floyd's algorithm, why does the pointer starting at the meeting point reach the cycle entry after exactly steps, even when is larger than the cycle length?
Answer
Because the meeting step is a multiple of , so . Starting at offset and moving steps lands at offset , the entry. Extra laps when do not change the offset.
7. Why can't an XOR linked list be implemented in Java or Python?
Answer
The garbage collector finds live objects by following references. An XOR of two addresses is not a reference, so the neighbours would look unreachable and be collected (or moved by a compacting collector). These languages also expose no portable way to turn an object into a raw address and back.