Description

LeetCode 23

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Analysis

Based on the idea of MergeSort, it is easy to come up with the method of selecting the minimum element each time. And extend the result linked list. The time of selecting the minimum element is \(O(k)\). And we need to do this when a new element is added. So the time of this method is \(O(kn)\).

However we could find more efficient methods to solve this problem. There are two directions.

First, if we observe this problem carefully, we could find the problem can be divided into subproblem recursively. And the subproblems could be merged easily. Remember if a problem satisfies these features, we should come up with Divide-and-Conquer method. For this problem, if we divide the k linked lists into two parts, the parts could be divided as this recursively. And the two parts could be merged by the method of merging two sorted lists. So is Divide-and-Conquer method efficient for this problem? Let’s look at the recursion.

$$T(k)=2T(k/2)+O(n)$$

Thinking of the recursive tree, the time is \(O(nlogk)\).

The second direction is that if we use the \(O(kn)\) method, we can find that we just change one element each time. If we select the minimum element one by one each time, some time is wasted. So a useful data structure is needed. It is the priority queue. It is based on heap. The feature of priority queue is we can return the minimum element with \(O(1)\). The time of adding a new element or deleting the minimum element are both \(O(logk)\). So we could use priority queue to store the linked lists. Then delete the minimum-value linked list of the priority queue and extend it to the result linked list. And add the next node of the head of the linked list to the priority queue. We should do this for all the elements. So the time of this method is \(O(nlogk)\).

Solution

//Merge with Divide And Conquer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        return helper(lists,0,lists.length-1);
    }
    public ListNode helper(ListNode[] lists,int low,int high)
    {
        if(low==high) return lists[low];
        int mid=(high-low)/2+low;
        return merge(helper(lists,low,mid),helper(lists,mid+1,high));
    }
    public ListNode merge(ListNode l1,ListNode l2)
    {
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val<l2.val)
        {
            l1.next=merge(l1.next,l2);
            return l1;
        }
        else
        {
            l2.next=merge(l1,l2.next);
            return l2;
        }
    }
}

//Priority Queue

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null||lists.length==0) return null;
        PriorityQueue<ListNode> pq=new PriorityQueue<>(lists.length,(a,b)->a.val-b.val);
        ListNode res=new ListNode(0);
        ListNode p=res;
        for(int i=0;i<lists.length;i++) { if(lists[i]!=null) pq.add(lists[i]); } while(pq.size()>0)
        {
            ListNode tmp=pq.poll();
            p.next=new ListNode(tmp.val);
            p=p.next;
            tmp=tmp.next;
            if(tmp!=null)
                pq.add(tmp);
        }
        return res.next;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/MergekSortedLists.java

[2] https://www.cnblogs.com/zywscq/p/5403051.html

[3] https://www.geeksforgeeks.org/divide-and-conquer-introduction/

[4] https://www.2cto.com/kf/201612/582345.html

Leave a Reply

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