Linked Lists

Picture a treasure hunt. You hold the first clue. It does not tell you where the prize is. It only tells you where the next clue is hidden. That clue points to the next one, and so on, until a clue says "this is the end".

To add a clue between the first and the second, nobody moves anything. The new clue points where the first one pointed, and the first clue now points at the new one. Two small edits, however long the hunt is. That is a linked list.

#Nodes and pointers

A linked list is a chain of nodes. Each node holds a value and a reference to the next node, usually called next. The last node's next is null (None in Python). You keep hold of the first node, called the head, and reach everything else by following arrows.

An array keeps items side by side, so it can jump to arr[1000] in one step, but inserting at the front shifts every item. A linked list makes the opposite trade: you cannot jump to position 1000, but inserting or removing next to a node you hold only rewires an arrow or two.

In code, a node is a tiny object. Walking the list means starting at the head and following next until you reach null. Insert and delete are one line each, as long as you already hold the node before the spot you want to change.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}
 
function printList(head) {
  const parts = [];
  for (let node = head; node !== null; node = node.next) parts.push(node.val);
  console.log(parts.join(" -> ") + " -> null");
}
 
function insertAfter(node, val) {
  node.next = new ListNode(val, node.next); // new node points where node pointed
}
 
function deleteAfter(node) {
  if (node.next !== null) node.next = node.next.next; // skip over it
}
 
// Build 4 -> 7 -> 2 -> 5 by adding at the front, last value first.
let head = null;
for (const v of [5, 2, 7, 4]) head = new ListNode(v, head);
insertAfter(head, 9);
printList(head); // 4 -> 9 -> 7 -> 2 -> 5 -> null

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
def print_list(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.val))
        node = node.next
    print(" -> ".join(parts) + " -> None")
 
def insert_after(node, val):
    node.next = ListNode(val, node.next)  # new node points where node pointed
 
def delete_after(node):
    if node.next is not None:
        node.next = node.next.next  # skip over it
 
# Build 4 -> 7 -> 2 -> 5 by adding at the front, last value first.
head = None
for v in [5, 2, 7, 4]:
    head = ListNode(v, head)
insert_after(head, 9)
print_list(head)  # 4 -> 9 -> 7 -> 2 -> 5 -> None

Order matters inside insertAfter. The new node grabs node.next first, and only then does node.next change. Reverse that and you lose the rest of the list.

#Reversing a list in place

Reversal is the classic drill for the "save before you overwrite" rule. The goal: flip every arrow, so 4 → 7 → 2 → 5 becomes 5 → 2 → 7 → 4, using no extra list.

The idea is to split the list into two parts as you walk. Behind you is a reversed chain, held by prev. In front of you is the untouched rest, starting at current. Each step moves one node from the front of the rest onto the front of the reversed chain.

prev = nullcurrent = headwhile current != null:  next = current.next  current.next = prev  prev = current  current = nextreturn prev

function reverse(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const next = current.next; // 1. save the rest of the list
    current.next = prev;       // 2. flip this node's arrow
    prev = current;            // 3. step both pointers forward
    current = next;
  }
  return prev; // the old last node is the new head
}

def reverse(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next   # 1. save the rest of the list
        current.next = prev  # 2. flip this node's arrow
        prev = current       # 3. step both pointers forward
        current = nxt
    return prev  # the old last node is the new head

An empty list needs no special case: the loop never runs and you return null.

#Fast and slow pointers

You cannot ask a linked list for its length or its middle without walking it. But you can walk it with two pointers at different speeds. slow takes one step at a time, fast takes two. This is the same-direction shape from Two Pointers, with speed as the twist.

#Finding the middle in one pass

When fast reaches the end, it has gone twice as far as slow. So slow is halfway. No counting, no second pass.

slow = head, fast = headwhile fast != null and fast.next != null:  slow = slow.next  fast = fast.next.nextreturn slow

With an even count there are two middles. For 10 → 20 → 30 → 40 → 50 → 60 this loop returns 40, the second one. For the first, loop while fast.next != null and fast.next.next != null, and handle an empty list before the loop.

#Detecting a cycle

If a bug makes the last node point back into the list instead of to null, a plain walk never ends. To notice, run the same two pointers. If there is no cycle, fast falls off the end. If there is a cycle, both pointers end up going round it, and fast gains one node on slow every round. The gap shrinks by one each time, so fast cannot jump over slow: they must land on the same node. It is two runners on a circular track: the faster one always laps the slower one.

slow = head, fast = headwhile fast != null and fast.next != null:  slow = slow.next  fast = fast.next.next  if slow == fast: return truereturn false

function middle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;      // one step
    fast = fast.next.next; // two steps
  }
  return slow;
}
 
function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // fast lapped slow
  }
  return false; // fast fell off the end
}

def middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next       # one step
        fast = fast.next.next  # two steps
    return slow
 
def has_cycle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # fast lapped slow
            return True
    return False  # fast fell off the end

Both run in O(n) time and O(1) space. For the cycle, slow enters the loop within n steps, and then the gap closes by one node per round, so they meet within another n rounds. A set of visited nodes also works, but costs O(n) memory.

#Common mistakes

#Check yourself

#What to practise next

Practise the save-flip-step loop on Reverse the Playlist and fast and slow pointers on Middle of the Parade. Next, Stacks look at a structure where you only ever touch one end, which a linked list does perfectly by adding and removing at the head.