### Question

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

### Stats

Frequency | 4 |

Difficulty | 3 |

Adjusted Difficulty | 5 |

Time to use | ---------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

There are two ways to solve this problem.

- k - number of lists
- n - length of each list

**First approach is merge sort**. Using divide and conquer approach, divide the entire input into halves, and then merge 2 list each time. Instead of merging 1 by 1 which the time complexity is O(nk x (k-1)), the 2 lists to be merged is always similar length, thus time complexity is reduced to O(nk x logk).

**You may wonder how I calculate time complexity**. See, each round of sort, nk nodes are read and sorted. This happened O(logk) times, where k is the number of lists. Thus totoal time take is O(nk x logk).

**Second approach is heap sort**. The idea of this is to always keep a sorted list of the head of each list. When we retrieve items from the heap, it only take O(logk) time to find the next smallest element.

Not sure what is a heap? Read **[Fundamental] Heap (data structure)** before you proceed.

Both method are well explained in this csdn blog. Time complexity analysis is given by nootcoder blog.

### Solution

Divide and conquer code is lengthy but medium difficulty.

Second solution, however, is not as easy. **Especially when we have to write Comparator on our own**. A priority queue (heap) is implemented and head of each list is inserted into the heap. Then poll elements out from the heap until heap is empty.

### My code

**Merge sort code, written by me**

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
return mergeHelper(lists, 0, lists.size() - 1);
}
private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
if (start == end) {
return lists.get(start);
}
int mid = start + (end - start) / 2;
ListNode firstHalf = mergeHelper(lists, start, mid);
ListNode secondHalf = mergeHelper(lists, mid + 1, end);
return mergeTwo(firstHalf, secondHalf);
}
private ListNode mergeTwo(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
p.next = head1;
head1 = head1.next;
p = p.next;
} else {
p.next = head2;
head2 = head2.next;
p = p.next;
}
}
if (head1 == null) {
p.next = head2;
} else {
p.next = head1;
}
return dummy.next;
}
}
```

**Heap sort code, written by me**. source

```
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
if (lists == null || lists.size() == 0) {
return null;
}
int size = lists.size();
// create a heap with Java priority queue, set the initial size
Queue<ListNode> heap = new PriorityQueue(size, new NodeComparator());
// add all ListNode into the heap
for (ListNode node: lists) {
if (node != null) {
heap.add(node);
}
}
// start to link nodes from smallest to largest
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (!heap.isEmpty()) {
p.next = heap.remove();
p = p.next;
if (p.next != null) {
heap.add(p.next);
}
}
return dummy.next;
}
class NodeComparator implements Comparator<ListNode> {
public int compare(ListNode n1, ListNode n2) {
return n1.val - n2.val;
}
}
}
```