# [LeetCode 23] Merge K Sorted Lists

### 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) {
p = p.next;
} else {
p = p.next;
}
}
if (head1 == null) {
} else {
}
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) {
}
}
// 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) {