Stop 21 · Data Structures & AlgorithmsTopics · 3/17

Linked List

In short

Linked list questions test one thing: can you move pointers without losing track of anything? Reverse a list on paper once and the rest gets much easier.

A linear data structure of nodes linked via pointers rather than contiguous memory — a classic interview topic for pointer manipulation practice.

Think of it like this

A treasure hunt

Each clue tells you where the next clue is hidden. You can't jump to clue 5; you follow them one by one. Lose a clue and everything after it is gone. A linked list is exactly that chain of clues.

Watch it happen

Reversing A → B → C

A→B

curr

B→C

C→null

1/5Three nodes, each pointing to the next. prev starts as null, curr starts at A.

The big ideas

What you need to know

Nodes and next pointers

Each node holds a value and a reference to the next node. The list only knows its head.

No index access

Finding the 5th item means walking 5 steps, so lookup is O(n). Inserting after a known node is O(1).

Fast and slow pointers

Move one pointer 1 step and another 2 steps. They meet if there's a cycle, and slow lands on the middle.

Dummy head trick

A fake node before the head removes special cases when the first node might be deleted or replaced.

See it in code

Walk through the code

1class ListNode {2  constructor(public val: number, public next: ListNode | null = null) {}3}4 5function reverse(head: ListNode | null): ListNode | null {6  let prev: ListNode | null = null;7  let curr = head;8  while (curr) {9    const next = curr.next; // save the rest of the list10    curr.next = prev;       // flip the arrow11    prev = curr;12    curr = next;13  }14  return prev; // the old tail is the new head15}

1/4A node is just a value plus a reference to the next node.

Three pointers, one loop, O(n) time and O(1) extra space. Draw boxes and arrows on paper the first few times.

Save yourself the pain

Common mistakes

Oops

Setting curr.next = prev before saving curr.next somewhere.

Do this instead

Always store const next = curr.next first. Otherwise the rest of the list is unreachable.

Oops

Not handling an empty list or a single node.

Do this instead

Test with null and with one node before submitting. Many pointer bugs only show up there.

Your mission

Pointer practice

~40 min

Quick check

Why is getting the 1000th item slower in a linked list than in an array?

Go deeper

1Implement a singly linked list from scratch (insert, delete, traverse).
2Solve classic problems: reverse a linked list, detect a cycle, find the middle node.
3Learn the 'fast and slow pointer' (tortoise and hare) technique.