get and set of java
Is normally used by private s to manipulate a class operation variable
The first method chooses a minimum value in each list at a time
Setting an initial value starts with k values and allows space

----Heapsort

In the node ListNode definition, a node is defined as a structure variable.
The node stores two variables: value and next.Value is the value of this node, next is the pointer to the next node, when next is a null pointer, this node is the last node in the chain table.
Note that value only represents the value of the current pointer, such as p->value for the pointer to p, and p->next for the next node in the list, is also a pointer.
The constructor contains two parameters _value and _next, which are used to assign values to nodes and specify the next node, respectively

Since Java version 1.5, a data structure with the nature of a small root heap, PriorityQueue, has been provided.

----//PriorityQueue The default is a small top heap, but a large top heap can be achieved by passing in a custom Comparator function.

Is actually a heap (defaults to the smallest heap when Comparator is not specified)
Queues can be sorted either by the natural order of the elements or by Comparator.
The header of the queue is the smallest element in the specified sort order.If multiple elements are minimum, the header is one of them.
When you create a new object, you can specify an initial capacity, which increases automatically.

- About dummy

1. Since you are not sure if the left and right parts are a little bit, you need to establish a dummy node on both sides.

2. left and right dummy and tail.Note: dummy is used as a virtual head for return.

Create a leftTail pointer and a rightTail pointer for the left and right sides to record the tails of the current two list s, respectively.This way, each time you get a new point, the size can be added directly to the corresponding tail.

3. For the last point of the right part, the next of the tail node is probably not empty, so rightTail->next = null will be handled on it

Chapter Nine Codes:

//You are generally restricted from using priority node because it is too simple

public class Solution{
	private comparator<ListNode> ListNodeComparator=new Comaprator<ListNode>(){
		public int compare(ListNode left, ListNode right){
			return left.val-right.val;
		}
	};
		
	
	
	public ListNode mergeKLists(List<ListNode> lists){
		if(lists==null||lists.size()==0){
			return null;
		}
		
		//Put the minimum value in the header of all the chains
		queue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),ListNodeComparator);//System-owned
		for(int i=0;i<lists.size();i++){
			if(lists.get(i)!=null){
				heap.add(lists.get(i));
			}
		}
		
		ListNode dummy=new ListNode(0);
		ListNode tail=dummy;
		while (!heap.isEmpty()){
			ListNode head=heap.poll();
			tail.next=head;
			tail=head;
			if(head.next!=null){
				heap.add(head.next);
			}
		}
		return dummy.next;
	}
}
			
			
		
		

This is very violent and complex

Method 2
Paired from bottom to top like a binary tree from bottom to

public ListNode mergeKlists(List<ListNode> lists){
	if(lists==null||lists.size()==0){
		return null;
	}
	
	while (lists.size()>0){
		List<ListNode> new_lists=new ArrayList<ListNode>();
		for (int i=0;i+1<lists.size();i+=2){
			ListNode merge_list=merge(lists.get(i),lists.get(i+1));
			new_lists.add(merge_list);
		}
		
		if(lists.size%2==1){
			new_lists.add(lists.get(lists.size()-1));
		}
		lists=new_lists;
	}
	
	return lists.get(0);
}

public ListNode merge(ListNode a,ListNode b){
	ListNode dummy=new ListNode(0);
	ListNode tail=dummy;
	while(a!=null&&b!=null){
		if(a.val<b.val){
			tail.next=a;
			a=a.next;
		}else{
			tail.next=b;
			b=b.next;
		}
	tail=tail.next;
	}
	
	if(a!=null){
		tail.next=a;
	}else{
		tail.next=b;
	}
	return dummy.next;
}

	

Method Three Most Important Merge Methods

public ListNode mergeKlists(List<ListNode> lists){
	if(lists==null||lists.size()==0){
		return null;
	}
	return mergeHelper(lists,0,lists.size()-1);
}

private ListNode mergeHelper(List<ListNode> lists, int start, int end){
	if(start==end){
		return lists.get(start);
	}
	
	int mid=start+(end-start)/2;
	ListNode left=mergeHelper(lists,start,mid);
	ListNode right=mergeHelper(lists,mid+1,end);
	return mergeTwoLists(left,right);
}
private ListNode mergeTwoLists(ListNode List1,ListNode list2){
	ListNode dummy=new ListNode(0);
	ListNode tail=dummy;
	while(list1!=null&&list2!=null){
		if(list1.val<list2.val){
			tail.next=list1;
			list1=list1.next;
		}else{
			tail.next=list2;
			list2=list2.next;
		}
	tail=tail.next;
	}
	
	if(list1!=null){
		tail.next=list1;
	}else{
		tail.next=list2;
	}
	return dummy.next;
}