Linked Lists

Intuition: a train of cars

Picture a train. Each car only knows the next car behind it: they're joined by a coupling. To reach the fifth car, you have to walk through the first four. On the other hand, adding a new car in the middle is easy: uncouple two cars, slot the new one between them, and couple everything back up. The rest of the train doesn't move at all.

That's a linked list:

• a node (a car) stores a value val and a reference next to the next node;
• the head (head) is the first node, the way into the list;
• the last node has next = null: there's nothing after it.

How a list differs from an array

An array is like a row of numbered slots packed tightly side by side. A list is a chain whose links are scattered all over memory.

Operation	Array	Linked list
Access by index i	O(1)	O(n): you walk from the head
Insert or delete when you have a reference to the neighbor	O(n): elements have to shift	O(1): just relink the references
Insert at the front	O(n)	O(1)
Extra memory	none	a pointer in every node

The key idea: in a list, changing the structure is cheap and searching is expensive. In interviews, almost every linked list problem comes down to handling references carefully.

Defining a node

You'll need this definition in every problem in this chapter:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # value
        self.next = next    # reference to the next node

Technique 1. The dummy head

Here's the annoying part of linked list problems: the head can change. Say you need to insert an element before the first node, or delete the first node itself. Your code starts sprouting checks like if head == null and if inserting at the front.

The fix is to create a dummy node dummy that sits before the head. Now every real node has a predecessor, and all cases are handled the same way. At the end, you return dummy.next.

Example: insert the number x into a sorted list.

def insert_sorted(head, x):
    dummy = ListNode(0, head)        # dummy node before the head
    prev = dummy
    while prev.next and prev.next.val < x:
        prev = prev.next             # find the node to insert after
    prev.next = ListNode(x, prev.next)
    return dummy.next                # the real head (it may have changed)

Notice that the empty list and inserting at the front both work without a single extra if.

Technique 2. In-place reversal with three pointers

The task: flip every arrow to point the other way, without creating new nodes.

You'll need three pointers:

• prev is the part that's already reversed, null at the start;
• curr is the current node, head at the start;
• next is a spare reference so you don't lose the tail.

At each step:

1. Save the tail: next = curr.next.
2. Flip the arrow: curr.next = prev.
3. Advance both pointers: prev = curr, curr = next.

When curr becomes null, prev holds the new head. Time O(n), memory O(1).

Draw the three steps on paper for a list of three nodes. Five minutes with a pen beats memorizing: after that, you won't mix up the order of the assignments.

Technique 3. Fast and slow pointers

Two pointers start at the head. The slow one (slow) takes 1 step, the fast one (fast) takes 2 steps.

The middle of the list. When fast reaches the end, slow is exactly in the middle: it has covered half the distance.

Loop condition: while fast and fast.next. That way fast never jumps into null.next.

Is there a cycle? If the tail of the list loops back to some node, fast will keep running in circles and sooner or later catch up with slow, the way a runner on a track laps someone who's walking. If they meet, there's a cycle. If you reach null, there isn't. Time O(n), memory O(1), no set of visited nodes needed.

How it sounds in an interview

• "I'll put a dummy node before the head so I don't have to special-case the first node changing."
• "I'll reverse it in place with three pointers: O(n) time, O(1) memory."
• "I'll use fast and slow pointers: the fast one moves two nodes at a time, so the slow one stops at the middle, and if there's a cycle, they'll meet."

Say the edge cases out loud: an empty list, one node, two nodes.

Common mistakes

• Losing the tail. You overwrote curr.next without saving it. Always save next first.
• Dereferencing null. You wrote fast.next.next without checking fast.next.
• Returning dummy instead of dummy.next.
• Moving head and losing the start of the list. Use a separate pointer for traversal.
• Forgetting the single-node case. Check that your loop works on the list [1].

You now know the three core linked list techniques: the dummy head, reversal, and two pointers. Next, you'll practice them on problems.