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
| Approach | Time | Space |
|---|---|---|
| Recursive | O(n) | O(n) |
| Iterative, three pointers | O(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 nullEach 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 = nextWhat 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 ← 3The 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 asnull, 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 previousWhen 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_headThe 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 2head.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 ← 3newHead 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. Aftercurrent.next = previous, the rest of the list is unreachable. Save first. - Starting
previousathead. The old head must end up pointing atnull. Ifpreviousstarts as the head, the head points at itself and the list becomes a loop. - Returning
headorcurrent. After the loopheadis the last node andcurrentisnull. The new head isprevious. - Leaving out
head.next = nullin 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
nullwithout a special case, and it is worth checking that any variation still does.
Original problem: LeetCode 206: Reverse Linked List