Merge Two Sorted Lists

Q: What is the time complexity of merging two sorted lists?

It is O(L1 + L2) : each comparison places one node, and no node is placed twice. With node objects the merge needs O(1) extra memory, since it only changes links. With the arrays used here, the shared link array costs O(L1 + L2) memory.

EasyLinked list Two pointers

+10

You get two singly linked lists, each stored in two arrays of the same length. In the first list, node i holds the value values1[i] and links to node next1[i]. The second list works the same way with next2 and values2. In both lists -1 ends the list and the head is node 0. The nodes are not stored in list order, so follow the links.

Each list is sorted in non-decreasing order along its links. Merge the two into one sorted list and return its values in order.

Function

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: the index of the node each node of the first list links to, or -1 for its last node
values1integer-array: the value held by each node of the first list
next2integer-array: the index of the node each node of the second list links to, or -1 for its last node
values2integer-array: the value held by each node of the second list
Returnsinteger-array: the values of the merged list, in order

Constraints

1 ≤ L1 ≤ 2000, where L1 is the length of next1 and of values1.
1 ≤ L2 ≤ 2000, where L2 is the length of next2 and of values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Each entry of next1 is -1 or a node index of the first list, and each entry of next2 is -1 or a node index of the second list.
Starting at node 0, each list visits every one of its nodes exactly once and then reaches -1. There is no cycle.
Along its links, each list is sorted in non-decreasing order.

Examples

Input: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Output: [1, 2, 3, 4, 6, 7, 9]
Explanation: Following the links, the first list visits nodes 0, 2, 1 and reads 1, 4, 6; the second reads 2, 3, 7, 9. Taking the smaller front each time gives 1, 2, 3, 4, 6, 7, 9.

Input: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Output: [-3, 0, 0, 5]
Explanation: The first list reads -3, 0, 5 and the second is the single value 0. Both 0s stay in the result, so it has four values.

Input: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Output: [1, 2, 3, 8, 10]
Explanation: The second list reads 1, 2, 3, all smaller than the 8 that starts the first list. The whole second list comes first, then 8, 10.

Follow-up

Can you merge k sorted lists in O(N log k) time, where N is the total number of nodes?

Hints

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

0 of 3 opened

Solution

Both lists are sorted, so the smallest value left is always at the front of one of them. Compare the two fronts, link the smaller one to the result, and step forward in that list. Sorting all N = L1 + L2 values also works, but it ignores that order and costs O(N log N).

Put every value in one array and sort it

Intuition

The merged list is the sorted version of all N values, so copy both value arrays into one and sort it. The order of the nodes inside the arrays does not matter, because the sort places every value. With N ≤ 4000 this is fast enough, but a sort costs O(N log N) comparisons where a merge needs at most N-1, and it never touches a link, the skill this problem tests.

Algorithm

Copy values1 and values2 into one array.
Sort the array in non-decreasing order.
Return it.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Splice the nodes behind a dummy head

Intuition

A pointer here is a node index. To link nodes of both lists into one chain, give them one numbering: node j of list 2 becomes node L1+j, with its links shifted the same way. A dummy node, number L1+L2, stands in front of the result.

Keep a and b on the first unused node of each list and tail on the end of the merged chain. Each step links tail to the smaller front and moves that pointer and tail forward. When one list runs out, the rest of the other is sorted and linked already, so one assignment attaches it. In the first example list 2 becomes nodes 3 to 6. After nodes 0, 3, 6, 2, 1, list 1 is empty and link[tail] = 4 attaches 7, 9.

Each node is linked at most once: O(N) time. The shared link array costs O(N) memory, where node objects would need none.

Algorithm

Build one link array: next1, then next2 shifted by L1 (leave -1 alone), then -1 for the dummy L1+L2. Build the matching values.
Set a = 0, b = L1 and tail to the dummy.
While neither a nor b is -1, link tail to the smaller (a on a tie), advance that pointer and move tail onto it.
Link tail to whichever of a and b is not -1.
Walk from link[dummy] to -1 and collect the values.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Pitfalls and edge cases

Merging the arrays in index order. The nodes are stored shuffled, so values1 itself is not sorted: in the first example it is [1, 6, 4]. Only the walk from node 0 is sorted.
Forgetting the leftovers. When one list runs out the loop stops, and dropping the rest of the other list loses the largest values: 7, 9 in the first example.
Advancing the wrong pointer, or both. Only the list whose node you took moves forward.
Mixing the two numberings. Node 2 of list 2 is not node 2 of list 1. Shift list 2's indexes and links by L1, and leave -1 as it is.

Frequently asked questions3

What is the time complexity of merging two sorted lists?

It is O(L1 + L2): each comparison places one node, and no node is placed twice. With node objects the merge needs O(1) extra memory, since it only changes links. With the arrays used here, the shared link array costs O(L1 + L2) memory.

Why use a dummy node when merging linked lists?

Without it, the first node of the result needs separate code, because there is no tail yet to link it after. The dummy is a placeholder head, so the first node is linked the same way as every other one. At the end you return the dummy's next node and the placeholder disappears.

Should you merge two sorted lists recursively or iteratively?

The recursive version is short: the smaller head links to the merge of everything else. But it uses one stack frame per node, so a list of a few thousand nodes can overflow the stack in some languages. The iterative loop with a tail pointer does the same work in constant stack space.

def mergeTwoLists(next1, values1, next2, values2):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Expected Output

[1, 2, 3, 4, 6, 7, 9]