合并K个升序链表---2022/02/26

题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题目来源

解题思路

这里有两种解法可以考虑：

首先是队列优先。思路是，把所有链表的头节点放入优先队列中。（补充说明：优先队列与先进先出队列不一样，每次取出的是具有最高优先级的元素。默认情况下，优先队列元素按照自然顺序排序，即数字小的在队头，字符串则按字典序排序。如果需要改变优先级的设定，需要实现Comparator接口。）而后将节点值值最小（涉及到优先级重新设定）的节点弹出，添加到新建链表中，而后再将该节点的下一节点添加到队列，直至队列为空。

其次是分治法。也就是一分为二（做前后分处理）的思想，需要借助的函数时合并两个升序链表。分到不可分为止，然后递归。
本题采用队列优先的方法。

代码实现

代码实现如下：

public ListNode mergeKLists(ListNode[] lists) {
    
			if(lists.length==0) return null;
			if(lists.length==1) return lists[0];
			ListNode head=new ListNode(0);
			ListNode cur=head;
			
			PriorityQueue<ListNode> pq=new PriorityQueue<>(new Comparator<ListNode>() {
    
				public int compare(ListNode o1,ListNode o2) {
    
					return o1.val-o2.val;//做升序处理，小的在队头
// return o2.val-o1.val;//做升序处理，小的在队头
				}
			});
			
			for(ListNode list:lists) {
    
				if(list==null)continue;
				pq.add(list);
			}
			while(!pq.isEmpty()) {
    
				ListNode nextNode=pq.poll();
				cur.next=nextNode;
				cur=cur.next;
				if(nextNode.next!=null) {
    
					pq.add(nextNode.next);
				}
			}
			return head.next;
		
		}

性能评估

发现了一个迷惑的操作。重复提交代码，内存性能持续降低，而时间性能不受影响。