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

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

^{2}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

^{2})].

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]

## No comments:

## Post a Comment