Linked Lists
How nodes and pointers form singly and doubly linked lists, how to rewire pointers safely, and the classic patterns: reversal, slow/fast pointers, cycle detection, merging and dummy heads.
What you will learn
How nodes and pointers form singly and doubly linked lists, how to rewire pointers safely, and the classic patterns: reversal, slow/fast pointers, cycle detection, merging and dummy heads.
Prerequisites: Module 4 (pointers and lifetime).
Types
Singly linked, doubly linked, circular singly linked, circular doubly linked, sentinel/dummy-head lists.
Text equivalent: head points to the node holding 3, whose next points to 7, then 9, whose next is nullptr. A doubly linked node also stores prev; a circular list's last node points back to the first.
flowchart TD
H[head] --> A[3]
A --> B[7]
B --> C[9]
C --> N[nullptr]Node syntax
struct Node {
int value;
Node* next;
explicit Node(int v) : value(v), next(nullptr) {}
};Operations
Create, traverse, search, insert at head/tail/position, delete by value/position, reverse, find middle, find nth from end, merge sorted lists, remove duplicates, and detect cycles.
Core patterns
Slow/fast pointers.
Dummy/sentinel node.
Floyd's cycle detection and cycle-entry finding.
Reverse in groups of k.
Sort a linked list using merge sort.
Flatten multilevel linked lists.
Example: iterative reversal
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Time O(n), auxiliary space O(1). Include pointer diagrams and empty/single-node tests. The key step is saving next before overwriting cur->next; losing it disconnects the rest of the list. The program frees every node, and AddressSanitizer's leak checker confirmed nothing leaked.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int value;
Node* next;
explicit Node(int v) : value(v), next(nullptr) {}
};
Node* reverseList(Node* head) {
Node* prev = nullptr;
Node* cur = head;
while (cur) {
Node* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
Node* build(const vector<int>& v) {
Node dummy(0); // dummy head: no special case for the first node
Node* tail = &dummy;
for (int x : v) { tail->next = new Node(x); tail = tail->next; }
return dummy.next;
}
string str(Node* h) {
string s;
for (; h; h = h->next) s += to_string(h->value) + (h->next ? " -> " : "");
return s.empty() ? "(empty)" : s;
}
void destroy(Node* h) { while (h) { Node* n = h->next; delete h; h = n; } }
Node* middle(Node* h) { // slow moves 1, fast moves 2
Node *slow = h, *fast = h;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
return slow;
}
Node* mergeSorted(Node* a, Node* b) {
Node dummy(0);
Node* t = &dummy;
while (a && b) {
Node*& smaller = (a->value <= b->value)
…reversed node 1: now points to nullptr
reversed node 2: now points to 1
reversed node 3: now points to 2
result: 3 -> 2 -> 1
(empty) reversed: (empty)
42 reversed: 42
1 -> 2 -> 3 -> 4 -> 5 reversed: 5 -> 4 -> 3 -> 2 -> 1
middle of 1..6 (second middle): 4
merged: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9Floyd's cycle detection
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Why the second phase works: if the tail before the cycle has length μ and the cycle has length λ, the meeting point is μ steps (mod λ) before the entry, so a pointer from the head and one from the meeting point, both moving one step, arrive at the entry together. Time O(n), space O(1).
#include <bits/stdc++.h>
using namespace std;
struct Node { int value; Node* next = nullptr; explicit Node(int v) : value(v) {} };
Node* cycleEntry(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // they met inside the cycle
Node* p = head;
while (p != slow) { p = p->next; slow = slow->next; }
return p; // both reach the entry together
}
}
return nullptr;
}
int main() {
vector<Node*> nodes;
for (int i = 0; i < 8; ++i) nodes.push_back(new Node(i));
for (int i = 0; i + 1 < 8; ++i) nodes[i]->next = nodes[i + 1];
cout << "no cycle: " << (cycleEntry(nodes[0]) ? "found" : "nullptr") << '\n';
nodes[7]->next = nodes[3]; // 7 -> 3 creates a cycle of length 5
cout << "cycle entry value: " << cycleEntry(nodes[0])->value << '\n';
for (Node* n : nodes) delete n;
}no cycle: nullptr
cycle entry value: 3Trade-offs
Linked lists offer O(1) insertion/deletion when the relevant node/position is already known, but locating an arbitrary position is O(n) and node allocation harms locality. Do not claim linked-list insertion is always O(1).
linkedlistEdge cases and common mistakes
Empty list and single node — test both for every operation.
Forgetting to update head when the first node is removed (a dummy head avoids it).
Dereferencing fast->next without checking fast.
Leaking or double-freeing nodes; using a node after delete.
Practice
Easy: delete every node with a given value (use a dummy head).
Medium: reverse nodes in groups of k, leaving a final short group unchanged.
Hard: copy a list whose nodes also have a random pointer, in O(n) time and O(1) extra space.
Quiz
? What must `reverseList` save before setting `cur->next = prev`?
+ `cur->next`, the rest of the list :: Otherwise the remaining nodes become unreachable.
- `prev->next` :: Already handled.
- The head pointer :: The new head is `prev` at the end.
- Nothing :: The rest of the list would be lost.
? Is inserting into a linked list always O(1)?
+ Only when you already hold the node/position; finding a position is O(n). :: The course stresses this distinction.
- Yes, always :: Searching costs O(n).
- No, always O(n) :: Head insertion is O(1).
- Only for doubly linked lists :: Singly linked head insertion is also O(1).
? Floyd's algorithm uses how much extra memory?
+ O(1) — two pointers :: A hash set of visited nodes would need O(n).
- O(n) :: That is the hash-set approach.
- O(log n) :: No.
- O(λ), the cycle length :: No.