Java实现 亚博体育LeetCode 23 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

PS：直接用PriorityQueue自动排序，改写一下compare方法。

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode(int x) { val = x; }

• }
  */
  class Solution {
  public ListNode mergeKLists(ListNode[] lists) {

  if (lists.length == 0) {
      return null;
  }
  
  ListNode dummyHead = new ListNode(0);
  ListNode curr = dummyHead;
  PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
      @Override
      public int compare(ListNode o1, ListNode o2) {
          return o1.val - o2.val;
      }
  });
  
  for (ListNode list : lists) {
      if (list == null) {
          continue;
      }
      pq.add(list);
  }
  
  while (!pq.isEmpty()) {
      ListNode nextNode = pq.poll();
      curr.next = nextNode;
      curr = curr.next;
      if (nextNode.next != null) {
          pq.add(nextNode.next);
      }
  }
  return dummyHead.next;

  }
  }

PS：分治

/**

• Definition for singly-linked list.
• public class ListNode {
• int val;
• ListNode next;
• ListNode(int x) { val = x; }

• }
  */
  class Solution {
  public ListNode mergeKLists(ListNode[] lists){
  if(lists.length == 0)
  return null;
  if(lists.length == 1)
  return lists[0];
  if(lists.length == 2){
  return mergeTwoLists(lists[0],lists[1]);
  }

  int mid = lists.length/2;
  ListNode[] l1 = new ListNode[mid];
  for(int i = 0; i < mid; i++){
      l1[i] = lists[i];
  }
  
  ListNode[] l2 = new ListNode[lists.length-mid];
  for(int i = mid,j=0; i < lists.length; i++,j++){
      l2[j] = lists[i];
  }
  
  return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

  }
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;

  ListNode head = null;
  if (l1.val <= l2.val){
      head = l1;
      head.next = mergeTwoLists(l1.next, l2);
  } else {
      head = l2;
      head.next = mergeTwoLists(l1, l2.next);
  }
  return head;

  }
  }
  4