Reverse Linked 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: Reversed, 0 → 1 → 2 → 3 becomes 3 → 2 → 1 → 0: each node links to the one before it, and node 0 links to -1.

Input: next = [2, -1, 3, 1]
Output: [-1, 3, 0, 2]
Explanation: Reversed, 0 → 2 → 3 → 1 becomes 1 → 3 → 2 → 0. Each new link sits at its node's index: [-1, 3, 0, 2], not the reversed array [1, 3, -1, 2].

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.

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 moves no node; it turns each link around. A node's link is your only way to the rest of the list, so once you overwrite it, everything after it is lost. Either write the order down first, or walk once and save the way forward before turning each link.

Write the order down, then relink

Intuition

A pointer here is a node index, and moving forward is node = next[node]. Walk from node 0 to -1 and write down the nodes: [0, 2, 3, 1] in the second example. In the reversed list each node links to the one before it in that order, and the old head links to -1. Write those links into a new array, so nothing is overwritten while you still need it.

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

Turn each link the moment you reach its node, and remember the node you came from in prev. It starts at -1, because the old head becomes the last node. Setting next[node] = prev erases your only way forward, so save it in after first.

At every moment the nodes behind you form a reversed list headed by prev, and the nodes ahead are untouched, starting at node. When node reaches -1, every link is turned and prev is the new head. In the second example the walk writes next[0] = -1, next[2] = 0, next[3] = 2 and next[1] = 3.

Each node is visited once, O(n) time, with three integers of memory.

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

Overwriting next[node] before saving it. The old forward link is gone, and the walk jumps backward instead of on to the next node.
Starting prev at 0 instead of -1. Node 0 then links to itself.
Reversing the array instead of the links. [2, -1, 3, 1] becomes [1, 3, -1, 2], not [-1, 3, 0, 2].
Looping while next[node] != -1. The last node's link is never turned; loop while node != -1.
In Lua and R arrays start at 1. Keep node indexes 0-based and read next[node + 1].

Frequently asked questions3

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.

def reverseList(next):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

[-1, 0, 1, 2]