Core pattern

Linked list: recoupling a train backwards

Learn the linked list pattern through one picture you won’t forget, worked on Reverse Linked List.

The example problem

Given the head of a singly linked list, reverse the list and return the new head.

Input:  1 → 2 → 3 → 4
Output: 4 → 3 → 2 → 1

Picture it

A linked list is like a train: each coach holds a value and a coupling to the next coach. The only way in is the first coach (the head). To reverse it, we walk along with three markers: prev (the part already reversed), curr (the coach we’re fixing) and nxt (the rest of the train, remembered so we don’t lose it). For each coach we flip its coupling to point backwards.

The key idea

Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.

Python

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Practise linked list

NeetCode 150 problems that use it

Linked List ·