23. Merge k Sorted Lists

Question:

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

Thinking:

• Method1: Merge every two lists

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            int len = lists.length;
            if(len == 0 )   return null;
            if(1 == len) return lists[0];
            ListNode result = new ListNode(0);
            result.next = lists[0];
            for(int i= 1; i < len; i++){
                result = mergeTwoList(result, lists[i]);
            }
            return result.next;
        }
        private ListNode mergeTwoList(ListNode result, ListNode mergeList){
            ListNode ans = new ListNode(0);
            ListNode dummy  = ans;
            ListNode head = new ListNode(0);
            head.next = mergeList;
            while(head.next != null || result.next != null){
                if(head.next != null && result.next != null){
                    if(head.next.val <= result.next.val){
                        ans.next = head.next;
                        head.next = head.next.next;
                    }else{
                        ans.next = result.next;
                        result.next = result.next.next;
                    }
                    ans = ans.next;
                }else if(head.next != null && result.next == null){
                    ans.next = head.next;
                    break;
                }else{
                    ans.next = result.next;
                    break;
                }
            }
            return dummy;
        }
    }
  

• Method2: Priority Queue: Use priority queue to select the minimum value.

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(null == lists || lists.length == 0) return null;
            int len = lists.length;
            ListNode result = new ListNode(0);
            ListNode temp = result;
            PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(len, new Comparator<ListNode>(){
                @Override
                public int compare(ListNode v1, ListNode v2){
                    return v1.val - v2.val;
                }
            });
            for(ListNode node:lists){
                if(null != node)    queue.offer(node);
            }
            while(!queue.isEmpty()){
                ListNode node = queue.poll();
                if(null != node){
                    temp.next = node;
                    temp = temp.next;
                    if(node.next != null)   queue.offer(node.next);
                }
            }
            return result.next;
        }
    }
  

二刷

1. 使用优先级队列。先将所有的结点加入优先级队列，然后将所有的结点出队列就能得到所有排列好的结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(0);
        ListNode cur = null;
        if(lists == null || lists.length == 0) return dummy.next;
        Queue<ListNode> pq = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            @Override
            public int compare(ListNode n1, ListNode n2){
                return n1.val - n2.val;
            }
        });
        for(ListNode head : lists){
            cur = head;
            while(cur != null){
                pq.offer(cur);
                cur = cur.next;
            }
        }
        cur = dummy;
        while(!pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }
}

Amazon session

• Method 1: divide and conquer ```Java /**
  • Definition for singly-linked list.
  • public class ListNode {
  • int val;
  • ListNode next;
  • ListNode(int x) { val = x; }
  • } */ class Solution { // we use divide and conquer to solve this question public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0) return null; return merge(lists, 0, lists.length - 1); } private ListNode merge(ListNode[] lists, int low, int high){ if(low == high) return lists[low]; else if(high == low + 1) return merge2Lists(lists[low], lists[high]); int mid = low + (high - low) / 2; ListNode lowList = merge(lists, low, mid); ListNode highList = merge(lists, mid + 1, high); return merge2Lists(lowList, highList); } private ListNode merge2Lists(ListNode first, ListNode second){ if(first == null && second == null) return null; else if(first != null && second != null){ ListNode node = first.val <= second.val ? first: second; if(first.val <= second.val) node.next = merge2Lists(first.next, second); else node.next = merge2Lists(first, second.next); return node; }else{ return first != null ? first: second; } } } ```