Linked Lists

Linked List Manipulation

Traverse, insert, delete and reverse nodes by rewiring pointers.

Easy, about 60 minutes to practise.

1Understand

The idea

A linked list is changed by rewiring next pointers, not by moving values. Before you overwrite a pointer, save what it pointed to. A dummy node in front of the head removes the special case of changing the first node, and reversing is three pointers: previous, current and next.

Intuition

A linked list changes by rewiring next pointers, not by moving values around. Before you overwrite a pointer, save what it pointed to, otherwise you lose the rest of the list.

A dummy node in front of the head removes the special case of changing the first node. Reversal is the three-pointer walk: previous, current, next.

Draw the pointers for one step; most bugs are a missing save or updating in the wrong order.

What you will be able to do

  • Use a dummy head to simplify edge cases
  • Save next before rewiring

When to use it

  • Input is a ListNode head
  • Reverse all or part of a list
  • Remove nodes matching a condition

2See it

Walkthrough

Reverse a list

1 → 2 → 3, save next, rewire cur.next to prev, advance.

1 / 4

SFi
1
2
3
012
S → index 0

prev = None, cur = head (1). Save nxt before rewiring.

prev, cur = None, head

Live template

Line 1 active

1prev, cur = None, head
2while cur:
3 nxt = cur.next
4 cur.next = prev
5 prev, cur = cur, nxt
6return prev

Complexity: time O(n), space O(1)

Reversal and most local rewires are O(n) time, O(1) extra space. Recursion uses O(n) stack. Dummy-head patterns for insert/delete are O(1) pointer changes once you have found the spot (finding is still O(n)).

Read the walkthrough as text

Reverse a list. 1 → 2 → 3 → None.

  1. prev = None, cur = 1.
  2. Save nxt = cur.next. Set cur.next = prev. Advance prev, cur = cur, nxt.
  3. After step on 1: None ← 1 2 → 3.
  4. After 2: None ← 1 ← 2 3. After 3: None ← 1 ← 2 ← 3. Return prev.

In code:

  • prev = None
  • cur = head
  • while cur:
  • nxt = cur.next
  • cur.next = prev
  • prev, cur = cur, nxt
  • return prev

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Reverse a list

    Example. Reverse a singly linked list in place.

    How. prev, cur, nxt walk: cur.next = prev, then shift all three.

  • Reverse a sub-range or k-group

    Example. Reverse every k nodes.

    How. Dummy head; reverse k links per segment, stitch ends between groups.

  • Delete nodes by value

    Example. Remove all nodes with val from a linked list.

    How. Dummy + prev pointer: skip nodes where cur.val == val by prev.next = cur.next.

  • Insert into a sorted list

    Example. Insert target into sorted linked list.

    How. Walk until prev.next.val > target, then splice new node between prev and prev.next.

  • Add numbers stored as lists

    Example. Two lists store digits MSB or LSB, add them.

    How. Reverse if needed, or add with carry walking both lists and building result digits.

  • Deep copy with a node map (random pointers)

    Example. Copy list where each node has next and random.

    How. Two passes: map old→new, then wire next and random via the map.

  • Rotate or split by length

    Example. Rotate list right by k places.

    How. Find tail and length, k %= n, break list at n−k, reattach tail before head.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Lost reference

    Why it happens. Rewiring `.next` before saving the successor cuts the list.

    How it fails. cur.next = prev before nxt = cur.next, you lose the rest of the list after cur.

    Fix. Always `nxt = cur.next`, then rewire, then advance with saved nxt.

  • Head edge case

    Why it happens. The first node is special for delete/insert problems.

    How it fails. Delete head node with val: prev is None, you skip wiring the new head.

    Fix. Start with `dummy.next = head` and keep a pointer before the current node.

  • Dangling tail

    Why it happens. Splitting or deleting without nulling the old tail `.next`.

    How it fails. Partition leaves last node of “less” chain pointing into “greater”, cycle when traversing.

    Fix. After split, set tail.next = None on each chain before joining.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons