题目描述：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
解法一：利用堆。
将K个链表的头节点放入堆中，然后依次取出，如果节点后面还有节点，就将节点继续放入堆中。
时间复杂度：O(kn*logk),n是链表中的元素个数，k是链表个数
空间复杂度：这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)。
import java.util.Comparator; import java.util.PriorityQueue; public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length < 0){ return null; } //定义优先队列，以及排序规则。 PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() { @Override public int compare(ListNode o1, ListNode o2) { return (o1.val - o2.val); } }); ListNode dummyNode = new ListNode(-1); ListNode curNode = dummyNode; //把k个链表的第一个节点放入堆中 for (int i = 0; i < lists.length; i++){ ListNode head = lists[i]; if(head != null){ queue.add(head); } } //不断的从堆中取出节点，如果节点还有下一个节点，就把下一个节点也放入堆中。 while(!queue.isEmpty()){ ListNode node = queue.poll(); curNode.next = node; curNode = curNode.next; if(node.next != null){ queue.add(node.next); } } curNode.next = null; return dummyNode.next; } }
解法二：可以将K个链表逐渐缩小成规模为1的K个链表进行比较，最后在合并成原始规模的链表
时间复杂度：O(kn*logk)
空间复杂度：递归会使用到 O(logk) 空间代价的栈空间。
public class Solution2 { public ListNode mergeKLists(ListNode[] lists) { if(lists == null || lists.length == 0){ return null; } return helper(lists,0,lists.length-1); } private ListNode helper(ListNode[] lists, int left, int right) { if(left == right){ return lists[left]; } int mid = left + (right - left) / 2; ListNode l1 = helper(lists,left,mid); ListNode l2 = helper(lists,mid + 1,right); return mergeTwoLists(l1,l2); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } if(l2 == null){ return l1; } if(l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l1,l2.next); return l2; } } }
原文：https://www.cnblogs.com/pxy-1999/p/13769884.html