/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return a.val-b.val; } }); ListNode ret = null, cur = null; for(ListNode node: lists) { if(null != node) { pq.add(node); } } while(!pq.isEmpty()) { ListNode node = pq.poll(); if(null == ret) { ret = cur = node; } else { cur = cur.next = node; } if(null != node.next) { pq.add(node.next); } } return ret; } }
思路：最小堆 java提供了该模块
