Reverse Linked List

Q: How do you reverse a linked list in place?

Walk the list with two pointers, prev starting at nothing and node starting at the head. At each node, save its next node, point its link at prev , then move prev and node one step forward. When node runs out, prev is the head of the reversed list.

Q: What is the time and space complexity of reversing a linked list?

The iterative version visits each node once, O(n) time, and keeps three pointers, O(1) extra space. Copying the order into an array first is also O(n) time but needs O(n) extra space. A recursive version uses O(n) space for the call stack.

EasyLinked list

+10

You get a singly linked list stored in the array next: node i links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, so follow the links.

Reverse the list by turning every link around, so the old last node becomes the head and node 0 becomes the last node, linking to -1. Return the updated next array, which has the same length as the input.

Function

reverseList(next: integer-array) → integer-array

nextinteger-array: the index of the node each node links to, or -1 for the last node
Returnsinteger-array: the next array of the reversed list

Constraints

1 ≤ next.length ≤ 5000
Each next[i] is -1 or a node index from 0 to next.length-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: next = [1, 2, 3, -1]
Output: [-1, 0, 1, 2]
Explanation: The list is 0 → 1 → 2 → 3. Reversed it is 3 → 2 → 1 → 0, so node 3 links to 2, node 2 to 1, node 1 to 0, and node 0 to -1.

Input: next = [2, -1, 3, 1]
Output: [-1, 3, 0, 2]
Explanation: The list is 0 → 2 → 3 → 1, and reversed it is 1 → 3 → 2 → 0. Writing each new link at its node's index gives [-1, 3, 0, 2]. Reversing the array itself would give [1, 3, -1, 2], which is not the same thing.

Input: next = [-1]
Output: [-1]
Explanation: One node is its own reverse. It stays the head and the tail, and it still links to -1.

+11 hidden tests on Submit

Follow-up

Can you reverse only the part of the list between position left and position right, and leave the nodes before and after it where they are?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Reversing a list does not move any node; it turns each link around. The catch is that a node's link is the only way to reach the rest of the list, so the moment you overwrite it, everything after it is lost. You can avoid the problem by writing the order down first, or you can walk once with three pointers that save the way forward before each link is turned.

Write the order down, then relink

Intuition

In this problem a pointer is a node index, and moving forward is node = next[node]. Walk from node 0 until you reach -1 and write down every node you pass. In the second example that gives the order [0, 2, 3, 1].

In the reversed list, every node links to the node that came before it in that order: 1 links to 3, 3 to 2, 2 to 0. The first node of the order, the old head, has nothing before it, so it links to -1. Fill a new array with those links and return it.

Because every link is written into a fresh array, nothing gets overwritten while you still need it, which makes this version hard to get wrong. It takes O(n) time and O(n) extra memory for the order and the new array.

Algorithm

Walk from node 0 to -1 and append each node to order.
Create a new array of the same length.
Set the entry of order[0] to -1.
For every k ≥ 1, set the entry of order[k] to order[k-1].
Return the new array.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Turn the links around in one pass

Intuition

You can turn each link the moment you reach its node, if you remember the node you came from. Keep prev, the node behind you, starting at -1 because the old head will become the last node. At node, the link next[node] points forward; set it to prev so it points backward.

That write destroys your only way forward, so save it first in a third variable, after = next[node]. Then turn the link, and move both pointers one step: prev = node, node = after. At every moment the nodes behind you form a reversed list headed by prev, and the nodes ahead are the untouched rest, starting at node. When node reaches -1, every link has been turned and prev is the new head.

In the second example the pointers move through nodes 0, 2, 3, 1, writing next[0] = -1, next[2] = 0, next[3] = 2 and next[1] = 3. Each node is visited once, O(n) time, and the only memory is three integers, O(1).

Algorithm

Set prev = -1 and node = 0.
While node is not -1, save after = next[node].
Set next[node] = prev.
Move on: prev = node, then node = after.
Return next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Pitfalls and edge cases

Almost every bug here is about the order of the three assignments, or about the two ends of the list.

Overwriting next[node] before saving it. After next[node] = prev the old forward link is gone, and the walk jumps backward instead of on to the next node.
Starting prev at anything other than -1. The old head must end the new list. Starting at 0 makes node 0 link to itself.
Reversing the array instead of the links. The nodes are not stored in list order, and the answer keeps every node at its own index; only the values change. Reversing [2, -1, 3, 1] gives [1, 3, -1, 2], not [-1, 3, 0, 2].
Stopping one node early with a loop on next[node] != -1. The last node's link must be turned too, so loop while node != -1.
Reversing with recursion on a long list. A list of 5000 nodes needs 5000 nested calls, past Python's limit of 1000.
Forgetting the offset in Lua and R, where arrays start at 1. Keep node indexes 0-based and read next[node + 1]. Ruby and R reserve the word next, so their starters name the parameter next_.

Frequently asked questions4

How do you reverse a linked list in place?

Walk the list with two pointers, prev starting at nothing and node starting at the head. At each node, save its next node, point its link at prev, then move prev and node one step forward. When node runs out, prev is the head of the reversed list.

What is the time and space complexity of reversing a linked list?

The iterative version visits each node once, O(n) time, and keeps three pointers, O(1) extra space. Copying the order into an array first is also O(n) time but needs O(n) extra space. A recursive version uses O(n) space for the call stack.

Can you reverse a linked list recursively?

Yes. Reverse everything after the head, then make the head's old next node point back at the head and set the head's link to nothing. It reads well, but it makes one nested call per node, so a long list can overflow the call stack. Python stops at 1000 calls by default, which a list of 5000 nodes exceeds.

Why does reversing a linked list need three pointers?

To turn a node's link you need the node itself and the node before it, which is two pointers. The third holds the node after it, because turning the link erases the only reference to the rest of the list. Without it, the walk cannot continue.

Python

def reverseList(next):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

next = [1, 2, 3, -1]

Expected

[-1, 0, 1, 2]