这是道hard题,在处理时需要用到优先队列(PriorityQueue),即我们将每个链表的头结点放入最小堆中,每次取出最小的结点插入最终返回的链表。
当优先队列中不存在结点时,我们就得到了需要的链表。
public ListNode mergeKLists(ListNode[] lists) { if(lists.length==0) return null; ListNode dummy=new ListNode(); ListNode p=dummy; PriorityQueue<ListNode> pq=new PriorityQueue<>(lists.length,(a,b) ->(a.val-b.val)); for(ListNode head :lists) { if(head!=null) pq.add(head); } while(!pq.isEmpty()) { ListNode node=pq.poll(); p.next=node; if(node.next!=null) { pq.add(node.next); } p=p.next; } return dummy.next; }