Linked Lists

A linked list trades random access for cheap insertion. You cannot jump to index k — you must follow k pointers — but splicing a node in or out is O(1) once you are holding the right reference. Every technique below exists because of that trade.

What a Linked List Actually Looks Like

Start with what you already know. An array is one unbroken block of memory. The computer knows where the block starts, so nums[3] is arithmetic: start address + 3 × item size. One calculation, no searching. That is why nums[3] costs the same as nums[0].

A linked list gives that up completely.

Three words you need first

Node — a small box holding two things: a value, and directions to the next box.

Pointer (also called a reference) — the directions. Not the next node itself, but where to find it. Think of a house address written on a slip of paper: the paper is not the house.

null — the address slot is empty. There is no next box. This is how a list says "the end". Python spells it None.

The boxes are scattered anywhere in memory. Nothing keeps them in order except each one knowing where the next one lives.

A linked list of four values

head▼

→

→null

Each box holds a value and an arrow. The last arrow points at null, which means 'stop here'.

You are only ever given head — the first box. Everything else is reached by following arrows. Lose head and the whole list is unreachable, even though every node still exists in memory.

Why you cannot jump to index 3

There is no block, so there is no arithmetic to do. To reach the fourth value you must walk.

Getting to index 3 — the only way there is

current▼

→

→null

steps0

Start at head. This is index 0. We want index 3, so we are not there yet.

1 / 4

An array computes the address. A linked list has to travel to it.

What you get in return

Now the payoff. Suppose you want to insert 9 after the first node.

In an array, every item after the insertion point has to shift one place to make room — O(n) work, and it gets worse the earlier you insert.

In a linked list, nothing moves. You change two arrows.

Inserting 9 after the first node

prev▼

→

→null

We are holding the node to insert after. Nothing else about the list matters.

1 / 3

The order of the two steps matters enormously. Reverse them and you overwrite your only route to the rest of the list.

This is the bug you will actually write

If you set prev.next = new_node first, the address of the old prev.next is gone. Nothing else in the program was holding it. The rest of the list — however long — is now unreachable and lost.

That single rule, save the address before you overwrite it, is behind almost every linked-list technique on this page.

Array versus linked list, side by side

	Array	Linked list
Memory layout	One continuous block	Scattered boxes joined by arrows
Get index `k`	`O(1)` — arithmetic	`O(n)` — walk there
Insert / delete at a held position	`O(n)` — shift everything after	`O(1)` — rewire two arrows
Insert / delete at the front	`O(n)`	`O(1)`
Extra memory	None	One pointer per node
Can you go backwards?	Yes, `k - 1`	No — arrows point one way only

That last row causes more trouble than it looks. Once you have walked past a node, it is gone unless you kept a reference. Several techniques below exist purely to work around it.

The Three Techniques

1. Careful pointer rewiring

The defining hazard: overwriting a next pointer destroys your only reference to the rest of the list. Always save before you overwrite.

Reverse Linked List — the canonical three-pointer dance

2. Fast and slow pointers

Two pointers moving at different rates turn several questions into a single pass.

Middle of the Linked List — one step versus two
Linked List Cycle II — Floyd's algorithm, with a distance proof

3. The dummy head

Create a throwaway node in front of the result. Every append becomes uniform, and the "what about the first node?" special case disappears.

Merge Two Sorted Lists — the clearest demonstration

Two habits that prevent most linked-list bugs

Check fast before fast.next. Both languages short-circuit left to right, so while fast and fast.next never dereferences null. Reversing the order crashes.

Use a dummy head whenever the head might change. Deletions at the front, merges, and insertions all get simpler.

Node Definitions

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

Identity vs. Value

A recurring source of wrong answers: two nodes holding the same number are not the same node. When a problem asks where two lists intersect, or whether a list revisits a node, compare with is in Python and === in TypeScript — never .val.

Intersection of Two Linked Lists — built entirely around this distinction

All Problems

Problem	Difficulty	Pattern
Reverse Linked List	Easy	Pointer Rewiring
Middle of the Linked List	Easy	Fast & Slow
Merge Two Sorted Lists	Easy	Dummy Head
Intersection of Two Linked Lists	Easy	Two Pointers
Linked List Cycle II	Medium	Floyd's Algorithm

Suggested order

Reverse Linked List first — it teaches the pointer discipline everything else depends on. Then Middle of the Linked List, which introduces fast and slow pointers gently before Linked List Cycle II pushes them much further.

Linked Lists

On this page