Linked Lists

Pointer manipulation fundamentals: reversing, merging, finding the middle, removing the n-th node from the end and detecting cycles, each in O(n) time and O(1) extra space.

Overview

A linked list stores a sequence as separate nodes. Each node holds a value and a pointer (a reference) to the next node. The list itself is just a pointer to the first node, called the head. The last node points to nothing (null in Java and JavaScript, None in Python).

Linked lists test one skill: changing pointers in the right order without losing part of the list. The problems are short, but one wrong assignment cuts the list or builds a loop. Nearly every problem is solved by a small set of moves: a dummy head, reversal, two pointers at different speeds, two pointers with a gap, and merging.

Linked list or array

An array keeps its items side by side in memory, so it can jump to any index at once. A linked list can only walk from the head. In exchange, once you hold a node, you can add or remove the node after it by changing one or two pointers, with no shifting.

Read item at index i — O(1) — O(i): walk from the head
Insert or delete at the front — O(n): shift everything — O(1)
Insert or delete after a node you hold — O(n): shift the rest — O(1)
Append at the end — O(1) amortized — O(1) with a tail pointer, O(n) without
Search for a value — O(n) — O(n)
Memory layout — one block, cache friendly — scattered nodes plus a pointer each

In practice arrays are faster for most workloads, because reading neighbors in memory is cheap for the CPU cache. Linked lists win when you splice nodes in and out often and already hold a pointer to the spot, as in an LRU cache.

Singly, doubly and circular

Singly linked — next — the simplest form — cannot step back; deleting a node needs its predecessor
Doubly linked — next and prev — walk both ways; delete a node you hold in O(1) — one more pointer per node, two pointers to fix on every change
Circular — the last node points back to the first — any node can be the start; round-robin loops — no null to stop at, so loops must stop at the start node

Java's LinkedList class is a doubly linked list, and to reach an index it walks from whichever end is closer. The Linux kernel's list is doubly linked and circular.

The dummy head

Many bugs come from the head itself changing: deleting the first node, or building a new list from nothing. A dummy head (also called a sentinel) is a spare node placed in front of the real head. Every real node now has a node before it, so one piece of code handles the first node and the middle nodes alike. At the end, return dummy.next.

Reversal, step by step

To reverse a list in place, walk it once with three pointers: prev (the reversed part so far), curr (the node being moved) and nxt (saved so the rest of the list is not lost). The order of the four assignments is the whole trick: save the next node, point the current node back, then move both pointers forward.

Here is the trace for 1, 2, 3.

start — null — 1 — empty
1 — 2 — 1.next = null — 1 — 2 — 1
2 — 3 — 2.next = 1 — 2 — 3 — 2, 1
3 — null — 3.next = 2 — 3 — null — 3, 2, 1

When curr is null, prev is the new head. The loop visits each node once: O(n) time and O(1) extra space. A recursive version is shorter to write but uses O(n) stack space.

Fast and slow pointers

Two pointers start at the head. The slow pointer moves one node per step and the fast pointer moves two. When fast reaches the end, slow has covered half the distance, so it stands at the middle.

Trace for 1, 2, 3, 4, 5 (the loop runs while fast and fast.next exist).

start — 1 — 1 — yes
1 — 2 — 3 — yes
2 — 3 — 5 — no: fast.next is null

Slow stops at 3, the middle. For an even length such as 1 to 6, the same loop stops at 4, the second of the two middle nodes. If a problem needs the first middle (to split a list in half, for example), start fast at head.next instead.

Detecting a cycle and finding where it starts

If the last node points back into the list, a plain walk never ends. With fast and slow pointers, fast either reaches null (no cycle) or enters the cycle and starts gaining on slow by one node per step. Because the gap shrinks by exactly one each step, fast cannot jump over slow, so they meet within one lap. This is Floyd's cycle-finding algorithm: O(n) time and O(1) space. A hash set of visited nodes also works but uses O(n) space.

start — 1 — 1
1 — 2 — 3 — no
2 — 3 — 5 — no
3 — 4 — 4 — yes

To find the start of the cycle, put one pointer back at the head, leave the other at the meeting node, and move both one step at a time. They meet at the cycle start.

start — 1 — 4 — no
1 — 2 — 5 — no
2 — 3 — 3 — yes: the cycle starts at 3

Why it works: say the cycle starts a nodes from the head, has length c, and the pointers meet b nodes into the cycle. Slow has walked a + b steps and fast twice that, and the extra distance fast covered is whole laps, so a + b is a multiple of c. So walking a more steps from the meeting point completes a lap and lands exactly on the cycle start, the same place a pointer reaches after a steps from the head.

Two pointers with a gap

To find the n-th node from the end in one pass, move a lead pointer n + 1 steps ahead of a trailing pointer, then move both until the lead falls off the end. The trailing pointer then stands just before the target, which is the node you need in order to delete it. Starting both at a dummy head makes removing the first node work too.

Trace: remove the 2nd node from the end of 1, 2, 3, 4, 5 (D is the dummy). Fast first moves 3 steps, to node 3.

after fast's head start — D — 3
1 — 1 — 4
2 — 2 — 5
3 — 3 — null

Slow stops at 3, so set 3.next = 3.next.next, which unlinks 4. The result is 1, 2, 3, 5.

Merging two sorted lists

Keep a tail pointer on the result, starting at a dummy. At each step, compare the two front nodes, attach the smaller one to the tail and advance in that list. When one list runs out, attach the rest of the other in one step. No new nodes are created.

Trace for 1, 3, 5 and 2, 4.

1 — 1 — 2 — 1 — 1
2 — 3 — 2 — 2 — 1, 2
3 — 3 — 4 — 3 — 1, 2, 3
4 — 5 — 4 — 4 — 1, 2, 3, 4
5 — 5 — empty — rest of A — 1, 2, 3, 4, 5

Using <= when the values tie takes the node from the first list, which keeps the merge stable.

Choosing the technique

Many harder problems chain these moves. Reorder List, for example, finds the middle, reverses the second half, then weaves the two halves together. Reverse Nodes in k-Group and palindrome checks are also reversal plus pointer bookkeeping; the LinkedList In-place Reversal and Fast & Slow Pointers topics go deeper on those patterns.

What you will be able to do

Say when a linked list beats an array and when it does not, with the costs in a table.
Reverse a list in place and trace the pointers on a three-node example.
Use fast and slow pointers to find the middle, detect a cycle and find where it starts, and explain why the method works.
Remove the n-th node from the end in one pass using a gap and a dummy head.
Merge sorted lists without creating new nodes, and combine these moves for harder problems.

When to use it

Problems that give you a list head and ask you to change links in place with O(1) extra space.
Detecting a cycle, or finding where it starts (fast and slow pointers).
Finding the middle node, or splitting a list in half.
Merging sorted sequences without allocating new nodes.
Reversing a whole list or part of it, or reordering nodes.
Designing structures that splice items in and out in O(1), such as an LRU cache (a hash map plus a doubly linked list).

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio