Notes
All notes

Reverse a Linked List: three pointers, one pass

Problem. Given the head of a singly linked list, reverse the list and return the new head. No new nodes, no array — just rewire the next pointers so the chain runs the other way.

Input:  1 -> 2 -> 3 -> 4 -> nil
Output: nil <- 1 <- 2 <- 3 <- 4      # head is now 4

A node is just a value plus a next pointer:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

The idea

You cannot reverse a singly linked list in place by walking forwards alone: the moment you flip curr.next you lose your only route to the rest of the list. So keep three pointers:

Each iteration does the same four moves:

  1. nxt = curr.next — remember where we were going.
  2. curr.next = prev — point the current node backwards.
  3. prev = curr — the reversed part now ends at curr.
  4. curr = nxt — step into the rest.

When curr falls off the end (nil), prev is the new head.

Dry run

Reverse 1 -> 2 -> 3 -> 4 -> nil. Before and after, it looks like this — note that the arrows are the only thing that actually moves:

\begin{tikzpicture}[
  n/.style={draw,thick,minimum width=1.05cm,minimum height=1cm,font=\large\bfseries},
  nil/.style={draw,thick,dashed,minimum width=1.05cm,minimum height=1cm,font=\small\ttfamily,text=black!55},
  a/.style={->,thick},
  t/.style={font=\small\ttfamily,text=black!70}
]
  \node[t] at (2.7,2.15) {input};
  \node[n] (a1) at (0,1.2) {1};
  \node[n] (a2) at (1.8,1.2) {2};
  \node[n] (a3) at (3.6,1.2) {3};
  \node[n] (a4) at (5.4,1.2) {4};
  \node[nil] (ar) at (7.2,1.2) {nil};
  \draw[a] (a1.east) -- (a2.west);
  \draw[a] (a2.east) -- (a3.west);
  \draw[a] (a3.east) -- (a4.west);
  \draw[a] (a4.east) -- (ar.west);

  \node[t] at (2.7,-0.25) {output};
  \node[nil] (bl) at (-1.8,-1.2) {nil};
  \node[n] (b1) at (0,-1.2) {1};
  \node[n] (b2) at (1.8,-1.2) {2};
  \node[n] (b3) at (3.6,-1.2) {3};
  \node[n] (b4) at (5.4,-1.2) {4};
  \draw[a] (b1.west) -- (bl.east);
  \draw[a] (b2.west) -- (b1.east);
  \draw[a] (b3.west) -- (b2.east);
  \draw[a] (b4.west) -- (b3.east);
\end{tikzpicture}

We start with prev = nil, curr = 1, nxt = 2. Throughout, the nodes stay where they are — the arrow between two nodes either points right (not reversed yet), left (reversed), or is absent at the moving boundary between the two parts. The current node is orange, already-reversed nodes are green, and the three pointers are labelled above the nodes they reference.

After iteration 1 — curr was 1. We saved nxt = 2, flipped 1.next to prev (which was nil), then advanced. The prefix 1 is now reversed and ends in nil.

\begin{tikzpicture}[
  n/.style={draw,thick,minimum width=1.05cm,minimum height=1cm,font=\large\bfseries},
  nil/.style={draw,thick,dashed,minimum width=1.05cm,minimum height=1cm,font=\small\ttfamily,text=black!55},
  done/.style={n,fill=green!35},
  cur/.style={n,fill=orange!45,very thick},
  a/.style={->,thick},
  plp/.style={font=\scriptsize\ttfamily,text=green!45!black},
  plc/.style={font=\scriptsize\ttfamily,text=orange!85!black},
  pln/.style={font=\scriptsize\ttfamily,text=black!70}
]
  \node[nil] (nl) at (-1.8,0) {nil};
  \node[done] (n1) at (0,0) {1};
  \node[cur] (n2) at (1.8,0) {2};
  \node[n] (n3) at (3.6,0) {3};
  \node[n] (n4) at (5.4,0) {4};
  \node[nil] (nr) at (7.2,0) {nil};
  \draw[a] (n1.west) -- (nl.east);
  \draw[a] (n2.east) -- (n3.west);
  \draw[a] (n3.east) -- (n4.west);
  \draw[a] (n4.east) -- (nr.west);
  \node[plp] at (0,0.95) {prev};
  \node[plc] at (1.8,0.95) {curr};
  \node[pln] at (3.6,0.95) {nxt};
\end{tikzpicture}

After iteration 2 — curr was 2. nxt = 3 was saved, 2.next flipped to 1, and the boundary moved one node right. The reversed prefix is now nil <- 1 <- 2.

\begin{tikzpicture}[
  n/.style={draw,thick,minimum width=1.05cm,minimum height=1cm,font=\large\bfseries},
  nil/.style={draw,thick,dashed,minimum width=1.05cm,minimum height=1cm,font=\small\ttfamily,text=black!55},
  done/.style={n,fill=green!35},
  cur/.style={n,fill=orange!45,very thick},
  a/.style={->,thick},
  plp/.style={font=\scriptsize\ttfamily,text=green!45!black},
  plc/.style={font=\scriptsize\ttfamily,text=orange!85!black},
  pln/.style={font=\scriptsize\ttfamily,text=black!70}
]
  \node[nil] (nl) at (-1.8,0) {nil};
  \node[done] (n1) at (0,0) {1};
  \node[done] (n2) at (1.8,0) {2};
  \node[cur] (n3) at (3.6,0) {3};
  \node[n] (n4) at (5.4,0) {4};
  \node[nil] (nr) at (7.2,0) {nil};
  \draw[a] (n1.west) -- (nl.east);
  \draw[a] (n2.west) -- (n1.east);
  \draw[a] (n3.east) -- (n4.west);
  \draw[a] (n4.east) -- (nr.west);
  \node[plp] at (1.8,0.95) {prev};
  \node[plc] at (3.6,0.95) {curr};
  \node[pln] at (5.4,0.95) {nxt};
\end{tikzpicture}

After iteration 3 — curr was 3. Saved nxt = 4, flipped 3.next to 2. Only the last node is still pointing at nil.

\begin{tikzpicture}[
  n/.style={draw,thick,minimum width=1.05cm,minimum height=1cm,font=\large\bfseries},
  nil/.style={draw,thick,dashed,minimum width=1.05cm,minimum height=1cm,font=\small\ttfamily,text=black!55},
  done/.style={n,fill=green!35},
  cur/.style={n,fill=orange!45,very thick},
  a/.style={->,thick},
  plp/.style={font=\scriptsize\ttfamily,text=green!45!black},
  plc/.style={font=\scriptsize\ttfamily,text=orange!85!black},
  pln/.style={font=\scriptsize\ttfamily,text=black!70}
]
  \node[nil] (nl) at (-1.8,0) {nil};
  \node[done] (n1) at (0,0) {1};
  \node[done] (n2) at (1.8,0) {2};
  \node[done] (n3) at (3.6,0) {3};
  \node[cur] (n4) at (5.4,0) {4};
  \node[nil] (nr) at (7.2,0) {nil};
  \draw[a] (n1.west) -- (nl.east);
  \draw[a] (n2.west) -- (n1.east);
  \draw[a] (n3.west) -- (n2.east);
  \draw[a] (n4.east) -- (nr.west);
  \node[plp] at (3.6,0.95) {prev};
  \node[plc] at (5.4,0.95) {curr};
  \node[pln] at (7.2,0.95) {nxt};
\end{tikzpicture}

After iteration 4 — curr was 4. nxt is nil, so after flipping 4.next to 3 the loop condition fails. prev is now 4, the head of the fully reversed list — that is what we return.

\begin{tikzpicture}[
  n/.style={draw,thick,minimum width=1.05cm,minimum height=1cm,font=\large\bfseries},
  nil/.style={draw,thick,dashed,minimum width=1.05cm,minimum height=1cm,font=\small\ttfamily,text=black!55},
  done/.style={n,fill=green!35},
  head/.style={n,fill=green!55,very thick},
  a/.style={->,thick},
  plp/.style={font=\scriptsize\ttfamily,text=green!45!black},
  plc/.style={font=\scriptsize\ttfamily,text=black!70}
]
  \node[nil] (nl) at (-1.8,0) {nil};
  \node[done] (n1) at (0,0) {1};
  \node[done] (n2) at (1.8,0) {2};
  \node[done] (n3) at (3.6,0) {3};
  \node[head] (n4) at (5.4,0) {4};
  \node[nil] (nr) at (7.2,0) {nil};
  \draw[a] (n1.west) -- (nl.east);
  \draw[a] (n2.west) -- (n1.east);
  \draw[a] (n3.west) -- (n2.east);
  \draw[a] (n4.west) -- (n3.east);
  \node[plp] at (5.4,0.95) {prev = new head};
  \node[plc] at (7.2,0.95) {curr = nil};
\end{tikzpicture}

The pointer that saves the day is nxt: it is the only thing standing between curr.next = prev and a lost tail.

The code

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next   # 1. save the rest
        curr.next = prev  # 2. flip the link
        prev = curr       # 3. advance prev
        curr = nxt        # 4. advance curr
    return prev           # new head

The same loop in Go:

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	curr := head
	for curr != nil {
		nxt := curr.Next
		curr.Next = prev
		prev = curr
		curr = nxt
	}
	return prev
}

Recursive version

The recursion says: reverse everything after me, then put me at the end of it. It is shorter but uses stack space proportional to the list.

def reverse_list(head):
    if head is None or head.next is None:
        return head          # empty list, or the last node: new head
    new_head = reverse_list(head.next)
    head.next.next = head    # the node after me should point back at me
    head.next = None         # and I am now the tail
    return new_head

Complexity

Version Time Extra space
Iterative \(O(n)\) \(O(1)\)
Recursive \(O(n)\) \(O(n)\) call stack

Both touch each node once. The iterative version is usually preferred: it is constant space and cannot blow the stack on a long list.

Edge cases