Leetcode 23 Merge k Sorted Lists

Leetcode 23 Merge k Sorted Lists


The problem description is as follow:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

 

 

Merge-Sort Approach

Edit Merge k Sorted Lists on GitHub

It is quite intuitive to think about merge-sort. This problem is a simple transform of the original merge sort problem. We just have to divide those k sorted lists into smaller groups, and do the sort and merge.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return mergeSort(lists,0,lists.length-1);
}
private ListNode mergeSort(ListNode[] lists, int l, int r) {
if(l<r) {
int m = (l+r)/2;
return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
}
return lists[l];
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
dummy.next = l1;
ListNode cur = dummy;
while(l1!=null && l2!=null) {
if(l1.val<l2.val) {
l1 = l1.next;
}
else {
ListNode next = l2.next;
cur.next = l2;
l2.next = l1;
l2 = next;
}
cur = cur.next;
}
if(l2!=null)
cur.next = l2;
return dummy.next;
}
}
public class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length==0) return null; return mergeSort(lists,0,lists.length-1); } private ListNode mergeSort(ListNode[] lists, int l, int r) { if(l<r) { int m = (l+r)/2; return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r)); } return lists[l]; } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); dummy.next = l1; ListNode cur = dummy; while(l1!=null && l2!=null) { if(l1.val<l2.val) { l1 = l1.next; } else { ListNode next = l2.next; cur.next = l2; l2.next = l1; l2 = next; } cur = cur.next; } if(l2!=null) cur.next = l2; return dummy.next; } }
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0)
            return null;
        return mergeSort(lists,0,lists.length-1);
    }
    private ListNode mergeSort(ListNode[] lists, int l, int r) {
        if(l<r) {
            int m = (l+r)/2;
            return merge(mergeSort(lists,l,m),mergeSort(lists,m+1,r));
        }
        return lists[l];
    }
    private ListNode merge(ListNode l1, ListNode l2) { 
        ListNode dummy = new ListNode(0);
        dummy.next = l1;
        ListNode cur = dummy;
        while(l1!=null && l2!=null) {
            if(l1.val<l2.val) {
                l1 = l1.next;
            }
            else {
                ListNode next = l2.next;
                cur.next = l2;
                l2.next = l1;
                l2 = next;
            }
            cur = cur.next;
        }
        if(l2!=null)
            cur.next = l2;
        return dummy.next;
    }
}

Similar to the analysis in Leetcode 148 Sort List, assume the maximum length of every list is 

n
n, the time complexity is function
T(k)
T(k), then we have 
T(k) = T(k/2) + O(n*k)
T(k) = T(k/2) + O(n*k).

According to Master Theorem,  

T(k) = O(n*klogk)
T(k) = O(n*klogk). The space complexity is  
O(logk)
O(logk), which is the depth of our recursive call.

 

 

Heap Approach

We can maintain a heap of size k and use heap-sort to return the smallest number in heap.

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size.
4. Pop a new smallest number ...
1. Put first number of each sorted list into the k-size heap. 2. Pop the smallest number, say x in heap. 3. Push x.next into the heap to maintain size. 4. Pop a new smallest number ...
1. Put first number of each sorted list into the k-size heap.
2. Pop the smallest number, say x in heap.
3. Push x.next into the heap to maintain size. 
4. Pop a new smallest number ...

 

Note that we can implement the heap with

PriorityQueue
PriorityQueue in Java:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)
return null;
//PriorityQueue is a heap that use heap-sort
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
new Comparator<ListNode>() {
public int compare(ListNode a, ListNode b) {
return a.val-b.val;
}
});
//add first node of each list to the heap
for (ListNode list : lists) {
if (list != null)
heap.add(list);
}
ListNode head = new ListNode(0);
ListNode p = head; // serve as a helper dummy node
while (heap.size() > 0) {
ListNode temp = heap.poll();
//poll() retrieves and removes the head of the heap
p.next = temp;
//keep adding next element of each list
if (temp.next != null)
heap.add(temp.next);
p = p.next;
}
return head.next;
}
}
public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) return null; //PriorityQueue is a heap that use heap-sort PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return a.val-b.val; } }); //add first node of each list to the heap for (ListNode list : lists) { if (list != null) heap.add(list); } ListNode head = new ListNode(0); ListNode p = head; // serve as a helper dummy node while (heap.size() > 0) { ListNode temp = heap.poll(); //poll() retrieves and removes the head of the heap p.next = temp; //keep adding next element of each list if (temp.next != null) heap.add(temp.next); p = p.next; } return head.next; } }
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
 
        //PriorityQueue is a heap that use heap-sort
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.length,
                new Comparator<ListNode>() {
                    public int compare(ListNode a, ListNode b) {
                        return a.val-b.val;
                    }
                });
 
        //add first node of each list to the heap
        for (ListNode list : lists) {
            if (list != null)
                heap.add(list);
        }
 
        ListNode head = new ListNode(0);
        ListNode p = head; // serve as a helper dummy node
 
        while (heap.size() > 0) {
            ListNode temp = heap.poll();
            //poll() retrieves and removes the head of the heap
            p.next = temp;
 
            //keep adding next element of each list
            if (temp.next != null)
                heap.add(temp.next);
 
            p = p.next;
        }
 
        return head.next;
    }
}

In case you are not familiar with Heap and HeapSort:

  • Get the smallest element in the heap requires 
    O(1)
    O(1)
  • Put a new element in the heap of size k requires 
    O(k)
    O(k)

Since we have 

n*k
n*k elements in total, the total time complexity will be 
O(nk*logk)
O(nk*logk). The space complexity will be the size of heap 
O(k)
O(k).

 

 

Further Thoughts

Using heap to get the smallest/biggest single number or top K biggest/smallest numbers is very useful in real life, especially in big data area. If you want to know the hottest 10 topics, musics in billions of them, maintaining a heap is one of the best ways to do it. I will further discuss this problem in the future.

 

Leave a Reply

Your email address will not be published. Required fields are marked *