Merge K ascending linked lists ---2022/02/26

Title Description

Here's an array of linked lists , Each list has been listed in ascending order .
Please merge all the linked lists into one ascending list , Return the merged linked list .
Title source

Their thinking

Here are two solutions to consider ：

The first is queue first . The train of thought is , Put all the head nodes of the linked list into the priority queue .（ Additional explanation ： Priority queues are different from FIFO queues , Each time, the element with the highest priority is taken out . By default , Priority queue elements are sorted in natural order , That is, the one with a small number is at the head of the team , Strings are sorted in dictionary order . If you need to change the priority setting , Need to achieve Comparator Interface .） Then minimize the node value （ It involves priority reset ） Pop up node , Add to the new linked list , Then add the next node of the node to the queue , Until the queue is empty .

The second is divide and conquer . That is, one is divided into two （ Do pre and post processing ） Thought , Merge two ascending linked lists when you need to use the function of . Until it can't be divided , Then a recursive .
This topic adopts the method of queue first .

Code implementation

The code implementation is as follows ：

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;// Do ascending processing , The small one is at the head of the team 
// return o2.val-o1.val;// Do ascending processing , The small one is at the head of the team 
				}
			});
			
			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;
		
		}

Performance evaluation

Found a confusing operation . Repeatedly submit code , Memory performance continues to degrade , Time performance is not affected .