题解 | #合并k个已排序的链表# [P1]

普通mergeSort

时间: O(nlogn)
空间: O(k) k为list的个数(所有list都会在递归栈上)
worstcase还是O(n), i.e.每个list的长度都为1 [{1},{2}, ... {n}]

import java.util.*;

public class Solution {
  public ListNode mergeKLists(ArrayList<ListNode> lists) {
    if (lists.size() == 0) return null;
    return mergeSort(0, lists.size()-1, lists);
  }
  
  // sort lists[l, r]
  ListNode mergeSort(int l, int r, ArrayList<ListNode> lists) {
    if (l == r) return lists.get(l);
    int mid = l + ((r-l)>>1);
    
    ListNode lList = mergeSort(l, mid, lists);
    ListNode rList = mergeSort(mid+1, r, lists);
    return merge(lList, rList);
  }
  
  ListNode merge(ListNode l1, ListNode l2) {
    ListNode sentinal = new ListNode(-1);
    ListNode last = sentinal;
    ListNode n1 = l1, n2 = l2;
    while (n1 != null || n2 != null) {
      if (n2 == null || (n1 != null && n1.val < n2.val)) {
        last.next = n1;
        n1 = n1.next;
      } else {
        last.next = n2;
        n2 = n2.next;
      }
      last = last.next;
    }
    return sentinal.next;
  }
}