合并K个有序链表

合并K个有序链表

问题

这个题目说的是，给你 K 个递增排序的单链表，你要把它们合成一个链表，并且保持递增排序。合成链表的节点直接使用 K 个链表中的节点即可，无需创建新节点。

比如说，给你以下 3 个有序链表：

1 -> 2 -> 4
1 -> 4 -> 8
0 -> 2

合并后的有序链表是：

0 -> 1 -> 1 -> 2 -> 2 -> 4 -> 4 -> 8

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), p = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val < l2.val) {
        p.next = l1;
        l1 = l1.next;
      } else {
        p.next = l2;
        l2 = l2.next;
      }
      p = p.next;
    }

    if (l1 != null) p.next = l1;
    if (l2 != null) p.next = l2;
    return dummy.next;
  }

  // Time: O(k*n), Space: O(1)
  public ListNode mergeKSortedListsOneByOne(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    ListNode result = null;
    for (ListNode list: lists) {
      result = mergeTwoSortedLists(result, list);
    }
    return result;
  }

  // Time: O(n*log(k)), Space: O(k)
  public ListNode mergeKSortedListsMinHeap(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    Queue<ListNode> q = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode list: lists)
      if (list != null)
        q.add(list);
    ListNode dummy = new ListNode(0), p = dummy;

    while (!q.isEmpty()) {
      ListNode min = q.poll();
      p.next = min;
      p = p.next;
      if (min.next != null) q.add(min.next);
    }
    return dummy.next;
  }

  private ListNode merge(ListNode[] lists, int start, int end) {
    if (start == end) return lists[start];
    if (start > end) return null;
    int mid = start + (end - start) / 2;
    ListNode left = merge(lists, start, mid);
    ListNode right = merge(lists, mid+1, end);
    return mergeTwoSortedLists(left, right);
  }

  // Time: O(n*log(k)), Space: O(log(k))
  public ListNode mergeKSortedListsDivideConquer(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return merge(lists, 0, lists.length-1);
  }

}