Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Reverse Linked List

Reverse a singly linked list in place by turning each link round as you walk along it. Iterative and recursive solutions in JavaScript and Python.

Updated Medium read: 6 min read

Approaches at a glance

ApproachTimeSpace
RecursiveO(n)O(n)
Iterative, three pointersO(n)O(1)

The problem

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

1 → 2 → 3 → 4 → 5 → null    becomes    5 → 4 → 3 → 2 → 1 → null
1 → 2 → null                becomes    2 → 1 → null
null (an empty list)        stays      null

Each node is an object with a value and a next reference to the following node. The last node's next is null. The goal is to rearrange the existing nodes by changing their next references, not to build a new list of copies.

A node, in each language. All the code on this page uses this shape:

JavaScript

// A node is any object with a value and a next.
const node = { value: 1, next: null };

Python

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

What reversing means

No node moves and no value changes. The only thing that changes is the direction of each arrow:

before:   1 → 2 → 3 → null
after:    null ← 1 ← 2 ← 3

The old head becomes the last node, so its next becomes null. The old last node becomes the head.

The iterative solution: three pointers

Walk along the list once, turning each arrow round as you pass it. This is the link-reversal technique from the linked list pointers pattern.

Turning an arrow round means setting current.next = previous. That overwrites the only reference to the rest of the list, so the following node has to be saved first. Hence three variables:

  • previous: the node behind, already reversed. It starts as null, because the old head will end up pointing at nothing.
  • current: the node whose arrow is being turned.
  • next: a saved reference to the node ahead.

JavaScript

function reverseList(head) {
  let previous = null;
  let current = head;
 
  while (current !== null) {
    const next = current.next; // 1. save the rest of the list
    current.next = previous;   // 2. turn this arrow round
    previous = current;        // 3. step forward
    current = next;            // 4. step forward
  }
  return previous;
}

Python

def reverse_list(head):
    previous = None
    current = head
 
    while current is not None:
        following = current.next  # 1. save the rest of the list
        current.next = previous   # 2. turn this arrow round
        previous = current        # 3. step forward
        current = following       # 4. step forward
    return previous

When the loop ends, current has run off the end and is null, and previous is on the last node visited, which is the new head.

Walkthrough

1 → 2 → 3 → null:

Step previous current next (saved) List so far
Start null 1 1 → 2 → 3 → null
1 1 2 2 null ← 1    2 → 3 → null
2 2 3 3 null ← 1 ← 2    3 → null
3 3 null null null ← 1 ← 2 ← 3

Each row shows the state after the four lines have run. The loop stops when current is null, and previous, the node holding 3, is returned.

Time O(n): each node is visited once. Space O(1): three references, whatever the length of the list.

The recursive solution

The same result can be described in terms of a smaller version of itself: to reverse a list, reverse everything after the first node, then attach the first node at the end.

JavaScript

function reverseListRecursive(head) {
  if (head === null || head.next === null) return head;
 
  const newHead = reverseListRecursive(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

Python

def reverse_list_recursive(head):
    if head is None or head.next is None:
        return head
 
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

The two lines after the recursive call are the whole trick. Suppose the list is 1 → 2 → 3 and the call for head = 1 has just had the rest reversed:

1 → 2 ← 3        newHead is 3; node 1 still points at node 2

head.next is node 2, which is now the last node of the reversed part. So head.next.next = head makes node 2 point back at node 1, and head.next = null makes node 1 the new end:

null ← 1 ← 2 ← 3

newHead is passed back up unchanged through every call: it is the old last node, found once at the bottom of the recursion.

Time O(n). Space O(n): each node gets its own call, and all of those calls are waiting on the call stack at the deepest point. For a very long list that can exceed the stack limit, which the iterative version never does.

Which to choose

Iterative Recursive
Extra space O(1) O(n) for the call stack
Risk on very long lists None Stack overflow
Best for Real code, and as a building block Showing you understand recursion

Use the iterative version by default. It is also the one that later problems build on: Reverse Nodes in k-Group runs this same loop on one stretch of the list at a time.

Try it yourself

Copy a solution from above, add the lines below, and run it. The Python version also needs the ListNode class from the top of the page. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

// Helpers: build a list from an array, and read one back.
const toList = (values) =>
  values.reduceRight((next, value) => ({ value, next }), null);
const toArray = (head) => {
  const values = [];
  for (let node = head; node !== null; node = node.next) {
    values.push(node.value);
  }
  return values;
};
 
console.log(toArray(reverseList(toList([1, 2, 3, 4, 5])))); // [5, 4, 3, 2, 1]
console.log(toArray(reverseList(toList([])))); // []

Python

# Helpers: build a list from a Python list, and read one back.
def to_list(values):
    head = None
    for value in reversed(values):
        head = ListNode(value, head)
    return head
 
def to_values(head):
    values = []
    while head is not None:
        values.append(head.value)
        head = head.next
    return values
 
print(to_values(reverse_list(to_list([1, 2, 3, 4, 5]))))  # [5, 4, 3, 2, 1]
print(to_values(reverse_list(to_list([]))))  # []

The comment after each line is the result you should see.

Common mistakes

  • Turning the arrow before saving next. After current.next = previous, the rest of the list is unreachable. Save first.
  • Starting previous at head. The old head must end up pointing at null. If previous starts as the head, the head points at itself and the list becomes a loop.
  • Returning head or current. After the loop head is the last node and current is null. The new head is previous.
  • Leaving out head.next = null in the recursive version. Node 1 and node 2 then point at each other, and walking the list never ends.
  • Forgetting the empty list. Both versions handle null without a special case, and it is worth checking that any variation still does.

Original problem: LeetCode 206: Reverse Linked List