合并K个已排序的链表

1、归并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.ArrayList;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0) return null;
        return mergeKLists(lists,0,lists.size() - 1);
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists,int low,int high) {
        if(low >= high) return lists.get(low);
        int mid = low +((high - low ) >> 1);
        ListNode l1 = mergeKLists(lists,low,mid);
        ListNode l2 = mergeKLists(lists,mid + 1,high);
        return merge(l1,l2);
    }
    private ListNode merge(ListNode l1,ListNode l2){
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                head.next = l2;
                l2 = l2.next;
            }else{
                head.next = l1;
                l1 = l1.next;
            }
            head = head.next;
        }
        head.next = (l1 == null) ? l2 : l1;
        return pre.next;
    }
}

2、小顶堆

import java.util.*;

public class Solution {
   public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0) return null;
        Queue<Integer> pq = new PriorityQueue<>();
        for (ListNode node : lists) {
            while (node != null) {
                pq.offer(node.val);
                node = node.next;
            }
        }
        ListNode cur =new ListNode(-1);
        ListNode pre = cur;
        while(!pq.isEmpty()){
            cur.next = new ListNode(pq.poll());
            cur = cur.next;
        }
        return  pre.next;
    }
}