Linked Lists

What is a linked list?

A linked list stores elements in nodes. Each node holds a value and a pointer to the next node:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

Unlike an array, nodes are not stored contiguously in memory - each can live anywhere on the heap. The only entry point is the head pointer. The last node's next is None. To reach the kth element, you walk k links from the head: there is no index arithmetic shortcut.

The trade-off: linked lists give O(1) insert/delete at a known pointer (no shifting needed), and pay for it with O(n) random access. Arrays are the inverse. Most real systems prefer arrays for their cache locality, but linked lists appear in a disproportionate share of interview problems.

Core operations

Operation	Time	Notes
Access by index	O(n)	Traverse from head
Traversal	O(n)	One pass
Insert at head	O(1)	Rewire two pointers
Insert at tail	O(n) or O(1)	O(1) with a tail pointer
Delete at head	O(1)	`head = head.next`
Delete (given prev)	O(1)	`prev.next = node.next`
Search	O(n)	Scan from head
Reverse	O(n)	Three-pointer in-place

Traversal is the atomic building block - every other operation starts here:

curr = head
while curr is not None:
    # process curr.val
    curr = curr.next

Deletion requires a reference to the preceding node so you can redirect its next. Deleting the head is a special case - there is no predecessor, so you just reassign head = head.next.

Key patterns

Reversal

Flip every node's next pointer so the list runs the other way - one pass, no extra memory.

When to use - the task is "reverse this list" or a slice of it, or the problem is easier read back-to-front (for example, checking a list against its reverse). Do it in place: that buys O(1) space, where copying into a new list or stack would cost O(n).

How it works - hold three pointers: prev, curr, next_node. Each step does three things - stash next_node = curr.next, point curr.next = prev, then move prev and curr forward one. The stash is mandatory: the moment you overwrite curr.next, that saved pointer is your only handle on the rest of the list. One pass, O(n) time, O(1) space; when curr runs off the end, prev is the new head.

VisualizationReversal

0/16

None

curr

list

curr

∅

prevnext

prev = None, curr = head (1). Walk the list flipping links.

def reverse_list(head):▶    prev = None▶    curr = head    while curr:        next = curr.next        curr.next = prev        prev = curr        curr = next    return prev

Note

Save before you redirect - next_node = curr.next must come before curr.next = prev. Reversing that order overwrites the only pointer to the rest of the list.

Fast/slow pointers

Two pointers move at different speeds - fast takes two steps for every one slow takes.

When to use - you need the middle node, or you need to know whether the list has a cycle, in one pass with O(1) space. The naive alternatives are worse: copy the list into an array (O(n) space), or walk it twice to count the length first.

How it works - each iteration, advance fast by two and slow by one. When fast reaches the tail it has traveled twice as far, so slow is at the midpoint. For cycle detection, a loop lets the faster pointer lap the slower one until they land on the same node; with no cycle, fast just falls off the end. Since fast jumps two at a time, check both fast and fast.next before you dereference.

VisualizationFast/slow pointers

0/4

meet?

false

steps

list

slowfast

-4

∅

slow = fast = head (3). Tail links to index 1.

def has_cycle(head):▶    slow = fast = head    while fast and fast.next:        slow = slow.next        fast = fast.next.next        if slow is fast:            return True    return False

Note

Both loop guards are required - while fast and fast.next not just while fast. On an even-length list fast.next.next dereferences None and crashes without the second check.

Two-pointer with offset

Put a fixed gap of n nodes between two pointers, then move them together so the gap never changes.

When to use - the problem is phrased relative to the end of a singly linked list ("the nth node from the end", "delete the nth-from-last"). You can't walk backward, and you'd rather not make the two passes that counting the length first would take.

How it works - advance fast n steps on its own, then move fast and slow together until fast reaches the last node. The constant n-node gap leaves slow on the predecessor of the nth-from-end - the exact node whose next you rewrite to delete. Put a dummy node before the head and the case where the target is the head itself stops being special. One pass, O(1) space.

VisualizationTwo-pointer with offset

0/7

gap

list

dummy

fastslow

∅

Dummy before head. fast and slow both start at dummy. Remove the 2th node from the end.

def remove_nth_from_end(head, n):▶    dummy = ListNode(0, head)▶    fast = slow = dummy    for _ in range(n):        fast = fast.next    while fast.next:        fast = fast.next        slow = slow.next    slow.next = slow.next.next    return dummy.next

Note

Stop at the tail, not past it - with an n-step head start, advancing both until fast is the last node leaves slow on the target's predecessor (what deletion needs). If you instead stop when fast becomes None, slow lands on the target itself. Trace a 3-node list with n=1 before committing.

Canonical examples

Reverse a linked list

Three pointers, one pass, no extra space. Before redirecting curr.next = prev, you must save next_node = curr.next - skipping that line severs the rest of the list permanently. After the loop, prev is the new head (old tail).

Try it

Python

Loading editor…

Tests

assert to_list(reverse(make_list(1, 2, 3))) == [3, 2, 1]

assert to_list(reverse(make_list(1))) == [1]

assert reverse(None) == None

Hints (3)

Detect a cycle

Floyd's algorithm uses two pointers at different speeds. Inside a cycle, fast gains one node per step on slow and will eventually lap it - they must collide. If fast reaches the end (None), there is no cycle.

Try it

Python

Loading editor…

Tests

n1, n2, n3 = Node(1), Node(2), Node(3)
n1.next = n2; n2.next = n3
assert has_cycle(n1)==False
n3.next = n1
assert has_cycle(n1)==True
assert has_cycle(None)==False

Hints (3)

When to reach for a linked list

The problem gives you nodes and asks you to rearrange pointers (reverse, merge, split, reorder).
You need an LRU cache - doubly linked list + hash map is the canonical O(1) solution.
The problem mentions a cycle - fast/slow pointers are the go-to.
You need to find the nth from the end - two-pointer with an n-step head start.
The problem involves merging two sorted lists - dummy head + two-pointer merge.
The problem involves potential head deletion (remove all nodes with value X) - dummy head.

Practice problems

Reverse Linked List - The fundamental pointer-reversal exercise.
Merge Two Sorted Lists - Dummy head pattern in its clearest form.
Linked List Cycle - Floyd's algorithm in its simplest form.
Remove Nth Node From End of List - n-step head start trick.
Palindrome Linked List - Fast/slow to find middle, then reverse second half and compare.
LRU Cache - Doubly linked list + hash map, the capstone linked list problem.