Reverse Linked List

The problem

You are given the head of a singly linked list. A singly linked list is a chain of nodes. Each node holds a value and a next pointer to the node after it. The last node points to null.

Reverse the list and return the new head.

Example 1

Input: head = [3, 8, 1, 6, 4]

Output: [4, 6, 1, 8, 3]

Every arrow now points the other way. The old tail, 4, is the new head.

Example 2

Input: head = [2, 9]

Output: [9, 2]

Two nodes swap places.

Example 3

Input: head = []

Output: []

An empty list stays empty.

Constraints

• 0 ≤ n ≤ 5,000, where n is the number of nodes
• −5,000 ≤ Node.val ≤ 5,000

Clarifying questions

Can the list be empty?

Yes. Then head is null, and we return null.

May we change the nodes, or must we build a new list?

Changing the nodes is fine. We return the head of the reversed list.

Singly or doubly linked?

Singly. Each node only knows the node after it, not the one before.

Can the list have a cycle?

No. It always ends at null.

Spot the pattern

A singly linked list can only be walked forward. To reverse it, each node must end up pointing at the node before it. So while walking, keep a pointer to the previous node, and turn one arrow at each step. This is the core linked list move, and many harder problems reuse it.

Solutions

Copy the valuesO(n), O(n) spaceIn placeO(n), O(1) space

Show all

Recursion also reverses the list in O(n) time, but its call stack holds n calls, so it uses O(n) memory like the copy.

Copy the values O(n), O(n) space

The idea

Walk the list and copy every value into an array. Then walk it again from the head, and write the values back, taking them from the end of the array. The first node gets the last value, and so on.

The arrows never move, only the values do. It is simple and correct, but the array costs n extra slots.

Walkthrough

values

1. values = []
2. node = head
3. while node:
4. values.append(node.val)
5. node = node.next
6. node = head
7. while node:
8. node.val = values.pop()
9. node = node.next
10. return head

Pass 1 reads every value into an array. Pass 2 writes them back from the end of the array.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Copy the values: read them into an array, then write them back in reverse.
    // Two passes, so O(n) time, but the array costs O(n) memory.
    public ListNode reverseList(ListNode head) {
        java.util.List<Integer> values = new java.util.ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) values.add(node.val);
        // The last value read must go into the first node, so take from the end.
        for (ListNode node = head; node != null; node = node.next) {
            node.val = values.remove(values.size() - 1);
        }
        return head;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two loops run one after the other, not one inside the other. Each run of the first reads one value. Each run of the second writes one value. Both are 1 step.

   1. values = []
   2. node = head
   3. while node:
   4. values.append(node.val)
   5. node = node.next
   6. node = head
   7. while node:
   8. node.val = values.pop()
   9. node = node.next
   10. return head

2. 2 Count the runs on Example 1

   Example 1 has 5 nodes. The first loop reads 5 values. The second writes 5 values.

   5 + 5 = 10 runs.

   node	0	1	2	3	4
   pass 1 reads	3	8	1	6	4
   pass 2 writes	4	6	1	8	3

   total

   5 + 5 = 10

3. 3 Write the count for any n

   Each loop visits every node once:

   n + n = 2n

   Check it with Example 1: 2 × 5 = 10.

4. 4 Keep only the part that grows fastest

   Drop the 2. Two passes instead of one do not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The array values holds one value per node, so it grows to n slots. The space is O(n).

   values (n values)node

In place O(n), O(1) space

The idea

Walk the list with two pointers: previous (the node behind) and current (the node we are on). At each node, turn its arrow back to previous. Then step both pointers forward.

There is one trap. Once current.next points back, the rest of the list is unreachable. So save current.next in next_node before changing it.

When current falls off the end, previous is the old tail, which is the new head.

The invariant: before each step, the nodes up to previous form a reversed list, and current is the head of the part not yet touched.

Walkthrough

1. previous, current = None, head
2. while current:
3. next_node = current.next
4. current.next = previous
5. previous = current
6. current = next_node
7. return previous

previous starts at null and current at the head. Everything left of current will be reversed. Everything from current on is untouched.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // In place: walk once and turn each arrow back to the node before it.
    // One pass and three pointers, so O(n) time and O(1) memory.
    public ListNode reverseList(ListNode head) {
        ListNode previous = null, current = head;
        while (current != null) {
            // Save the rest of the list before we cut the link to it.
            ListNode nextNode = current.next;
            current.next = previous;
            previous = current;
            current = nextNode;
        }
        // current fell off the end, so previous is the old tail: the new head.
        return previous;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does four pointer moves. That is the same small job every time, so each run is 1 step. There is one loop.

   1. previous, current = None, head
   2. while current:
   3. next_node = current.next
   4. current.next = previous
   5. previous = current
   6. current = next_node
   7. return previous

2. 2 Count the runs on Example 1

   Example 1 has 5 nodes. current visits each of them once, then becomes null and the loop stops.

   5 runs.

   	run 1	run 2	run 3	run 4	run 5	stop
   current	3	8	1	6	4	null

3. 3 Write the count for any n

   The loop runs once per node:

   n times

   Check it with Example 1: 5 nodes, 5 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps three pointers: previous, current and next_node. That is 3 variables, for any n, so the space is O(1). No new nodes are made.

   previouscurrentnext_node

Common mistake

Returning head instead of previous

After the loop, head still points to the first node of the input. That node is now the tail, and its next is null. So returning head gives a list of one node. Return previous.

Tested at the limits

2,000 random lists of 0 to 8 nodes, so the empty list and the single node come up often. Copying the values and reversing in place gave the same list every time.

Largest inputs	Result
5,000 nodes (the most allowed). In place.	Under 0.001 s, and under 0.001 MB of extra memory: just three pointers.
5,000 nodes. Copy the values.	Under 0.001 s, and about 0.04 MB of extra memory: an array of 5,000 values, which is the O(n) space.