23.md

23. Merge K sorted Lists

Description

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

Thinking Process

1. The problem is similar to that of merge sort
2. Using divide and conquer, merge half of the lists first, then merge the result with the other half

Code

public class Solution{
  public ListNode mergeKLists(ListNode[] lists){
    if(lists.length == 0)
      return null;
    return merge(lists, 0, lists.length - 1);
  }
  
  ListNode merge(ListNode[] lists, int from, int to){
    if(from > to)
      return null;
    if(from == to)
      return lists[from];
    else{
      int mid = from + (to - from) / 2;
      return mergeTwoLists(merge(lists, from, mid), merge(lists, from + 1, to));
    }
  }
  
  ListNode mergeTwoLists(ListNode l1, ListNode l2){
    if(l1 == null && l2 == null)
      return null;
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while(l1 != null || l2 != null){
      int val1 = l1 == null ? Integer.MAX_VALUE : l1.val;
      int val2 = l2 == null ? Integer.MAX_VALUE : l2.val;
      if(val1 <= val2){
        current.next = l1;
        l1 = l1.next;
      }else{
        current.next = l2;
        l2 = l2.next;
      }
      current = current.next;
    }
    return dummy.next;
  }
}

Complexity

1. The program has O(1) space complexity, since no ListNode is duplicated. The returned value is merely a rearrangement of the existing ListNodes
2. Time complexity is O(nlogn)