Sort List

+10

You get a singly linked list stored in two arrays of the same length. Node i holds the value values[i] and links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, and the arrays may also hold leftover nodes that the walk from node 0 never reaches. Those are not part of the list, even when their links point into it.

Sort the list in non-decreasing order of value and return the values of its nodes in that order.

Function

sortList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: the index of the node each node links to, or -1 for the last node
valuesinteger-array: the value held by each node
Returnsinteger-array: the values of the list's nodes, smallest first

Constraints

1 ≤ n ≤ 4000, where n is the length of next and of values.
-1000 ≤ values[i] ≤ 1000
Each next[i] is -1 or a node index from 0 to n-1.
Starting at node 0, the list reaches -1 without visiting a node twice.
Nodes the walk from node 0 does not reach are not part of the list. Their next entries may point anywhere.

Examples

Input: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
Output: [1, 2, 3, 4, 5]
Explanation: The walk from node 0 visits nodes 0, 3, 2, 4, 1, so the list reads 4, 2, 3, 5, 1. Sorted, that is 1, 2, 3, 4, 5.

Input: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
Output: [-2, 6]
Explanation: The list is 0 → 2, which reads 6, -2. Nodes 1 and 3 are never reached from the head, so their values 9 and 5 are left out, even though node 1 links to node 0.

Input: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
Output: [-1, -1, 3, 3]
Explanation: The list reads 3, -1, 3, -1. Equal values stay in the answer as many times as they appear: -1, -1, 3, 3.

Follow-up

Can you sort by relinking the nodes in O(n log n) time, without copying the values out?

Solution

Quicksort and heapsort rely on random access, and a singly linked list only moves forward. Merge sort fits: splitting a list at its middle and merging two sorted lists both walk forward, so it sorts the links themselves in O(n log n). Here n is the length of the arrays.

Copy the values into an array and sort it

Intuition

The list is whatever the walk node = next[node] visits from node 0 until -1. Collect those values into a new array, sort it with the built-in sort, and return it. You cannot sort values directly: in the second example it holds 9 and 5, which are not on the list.

The walk is O(n) and the sort O(n log n), with O(n) extra memory. The list itself is never touched, which is why interviewers ask for the next approach.

Algorithm

Start with an empty array and node = 0.
While node is not -1, append values[node] and move to next[node].
Sort the array in increasing order and return it.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

Merge sort on the links

Intuition

A slow pointer that moves one link and a fast pointer that moves two find the middle in one walk. Merging two sorted lists needs only their front nodes: take the smaller one and step past it. Neither step needs a second array.

In the first example, slow stops on the 3, and cutting its link splits 4, 2, 3, 5, 1 into 4, 2, 3 and 5, 1. These sort to 2, 3, 4 and 1, 5, and the merge takes 1, 2, 3, 4, then links the leftover 5.

Each level of splitting touches every node a constant number of times, and there are about log n levels, so the time is O(n log n). The only extra memory is the recursion stack, about 12 calls deep for 4000 nodes.

Algorithm

If the list has one node (next[head] == -1), return head.
Start slow = head and fast = next[head]; move slow one link and fast two while fast and next[fast] are not -1.
Let second = next[slow] and cut with next[slow] = -1.
Sort both halves recursively. Merge them: link the smaller front node after tail until one half is empty, then link the rest of the other.
Walk from the returned head and collect the values.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Pitfalls and edge cases

Sorting the whole values array. In the second example that brings in 9 and 5, which are not on the list.
Starting fast on the head. With two nodes, slow then lands on the second node, the cut leaves an empty second half, and the recursion never shrinks.
Forgetting the cut next[slow] = -1. The first half then runs into the second, and both calls sort overlapping lists.
Dropping the rest of a half when the other runs out. Those nodes vanish from the result.
In Lua and R, arrays start at 1: keep node indexes 0-based and read next[node + 1]. The R version copies the link array once, so it uses O(n) extra memory.

Frequently asked questions3

What is the best way to sort a linked list?

Merge sort. Splitting at the middle, sorting both halves and merging them all walk the list forward, the only direction a singly linked list supports. It runs in O(n log n) time and relinks the existing nodes.

Why is merge sort preferred over quicksort for linked lists?

Quicksort can partition a list by relinking, but a good pivot needs random access, and taking the head as pivot makes a sorted list cost O(n²). Merge sort always splits in half, so it stays O(n log n) on any input.

Can you sort a linked list in O(n log n) time and O(1) memory?

Yes, with bottom-up merge sort. It merges neighbouring runs of length 1, then 2, then 4, until one run covers the list. There are log n linear passes, and the only memory is a few node indexes.

def sortList(next, values):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next = [3, -1, 4, 2, 1]
values = [4, 1, 3, 2, 5]

Expected Output

[1, 2, 3, 4, 5]