Merge multiple sorted linked lists

Return one sorted linked list for multiple sorted linked lists in below structure. Individual lists are sorted and the heads are also sorted. There are duplicates. Efficiency is not important.

x
1------>3------>5 //heads
|       |       |
3       5       7
|       |       |
5       6       9
                |
                10

Node:
    value
    Node next
    Node nextList // head of the next list

Node mergeSortedLists(Node x) //where x is top left node with value 1

Do a 2-way merge on the 1st two lists and use the resultant list to merge the next list and so on. I found it very tempting to not do it in-place but doing it in-place is cleaner.

Node mergeTwoLists(Node x, Node y):
    if x == null && y == null:
        return null
    if x == null:
        return y
    if y == null:
        return x
    Node start = x.value <= y.value ? x : y // pick x when x, y are equal
    while x != null && y != null:
        x = interleave(x, y)
        y = interleave(y, x)
    return start

// advance first list and link to 2nd list
void interleave(Node a, Node b):
    if a == null || b == null:
        return null
    Node preva = null
    while a != null && a.value <= b.value:
        preva = a
        a = a.next
    if preva != null:
        preva.next = b
    return a

A simpler way is to pick the min of x and y as the next node.

node mergeTwoLists(x, y):
    if x == null && y == null:
        throw
    head = n = null
    while x != null || y != null:
        min = min(x, y)
        if x == min:
            x = x.next
        if y == min:
            y = y.next
        if head == null:
            head = n = min
        else:
            n.next = min
            n = n.next
    return head

node min(x, y):
    if x == null && y == null:
        throw
    if x == null:
        return y
    if y == null:
        return x
    return x.value <= y.value ? x : y

cases:
x       y
1       3
|       |
3       5
|       |
5       6

x       y
3       1
|       |
5       3
|       |
6       5

x       y
1       2

x       y
2       1

Then wrap the 2-way merge to merge multiple lists.

Node mergeSortedLists(Node x):
    if x == null:
        return null
    Node y = x.nextList
    while y != null:
        x = mergeTwoLists(x, y)
        y = y.nextList
    return x

time is O(m²n) and space O(1) where there are m lists and average of n numbers per list. We go through the 1st list m times and last list 1 time [mn + (m-1)n + (m-2)n + ... + (1)n = n(m + m-1 + m-2 ... + 1) = nm(m+1)/2= O(nm²)].

A better way is to use min-heap and do a m-way merge in O(m * logm * n) time and O(m) space.

[Hat tip to M]