23. Merge k Sorted Lists.md

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;
    }
}

Third Time

• Method 1: Divide and conqur

   /**
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   class Solution {
   	private ListNode[] l;
   	public ListNode mergeKLists(ListNode[] lists) {
   		if(lists.length == 0) return null;
   		else if(lists.length == 1) return lists[0];
   		this.l = lists;
   		return sort(0, this.l.length - 1);
   	}
   	private ListNode sort(int low, int high){
   		if(low >= high) return l[low];
   		int mid = low + (high - low) / 2;
   		ListNode l1 = sort(low, mid);
   		ListNode l2 = sort(mid + 1, high);
   		return merge(l1, l2);
   	}
   	private ListNode merge(ListNode l1, ListNode l2){
   		ListNode dummy = new ListNode(0), cur = dummy;
   		ListNode first = l1, second = l2;
   		while(first != null || second != null){
   			if(first != null && second != null){
   				cur.next = first.val < second.val ? first: second;
   				if(first.val < second.val) first = first.next;
   				else second = second.next;
   			}else if(first != null){
   				cur.next = first;
   				break;
   			}else{
   				cur.next = second;
   				break;
   			}
   			cur = cur.next;
   		}
   		return dummy.next;
   	}
   }

Fourth Time

• Method 1: Divede and Conquer

  /**
   * Definition for singly-linked list.
   * public class ListNode {
   *     int val;
   *     ListNode next;
   *     ListNode(int x) { val = x; }
   * }
   */
  class Solution {
      private ListNode[] lists;
      public ListNode mergeKLists(ListNode[] lists) {
          if(lists == null || lists.length == 0) return null;
          else if(lists.length == 1) return lists[0];
          this.lists = lists;
          return sort(0, lists.length - 1);
      }
      private ListNode sort(int low, int high){
          if(low == high) return this.lists[low];
          int mid = low + (high - low) / 2;
          ListNode l1 = sort(low, mid);
          ListNode l2 = sort(mid + 1, high);
          return merge(l1, l2);
      }
      private ListNode merge(ListNode l1, ListNode l2){
          ListNode dummy = new ListNode(0), cur = dummy;
          while(l1 != null || l2 != null){
              if(l1 != null && l2 != null){
                  cur.next = l1.val < l2.val ? l1: l2;
                  if(l1.val < l2.val) l1 = l1.next;
                  else l2 = l2.next;
              }else if(l1 != null){
                  cur.next = l1;
                  l1 = l1.next;
              }else{
                  cur.next = l2;
                  l2 = l2.next;
              }
              cur = cur.next;
          }
          return dummy.next;
      }
  }