用Java合并K排序链表
给定K个可变大小的链表，这些链表按它们的顺序排序，我们必须将列表合并到结果列表中，结果数组按顺序排序，结果数组作为输出打印给用户。
让我们用例子来理解：-
输入 -
整数k=3;
列表[0]=新节点(11)；
list[0].next=新节点(15)；
list[0].next.next=新节点(17)；
列表[1]=新节点(2)；
list[1].next=newNode(3);
list[1].next.next=新节点(26)；
list[1].next.next.next=新节点(39)；
列表[2]=新节点(4)；
list[2].next=newNode(8);
list[2].next.next=newNode(10);
输出 -合并后的列表是-->
2>>3>>4>>8>>10>>11>>15>>17>>26>>39>>空
解释 -我们给出了K个按顺序排序的链表。合并过程包括使用java比较器函数比较链表的头部并将它们合并到结果数组中。
输入 -
整数k=2;
列表[0]=新节点(1)；
list[0].next=newNode(4);
list[0].next.next=newNode(5);
列表[1]=新节点(2)；
list[1].next=newNode(3);
list[1].next.next=newNode(6);
list[1].next.next.next=newNode(8);
输出 -合并列表是-->
1>>2>>3>>4>>5>>6>>8>>空
解释 -我们给出了K个按顺序排序的链表。合并过程包括使用java比较器函数比较链表的头部并将它们合并到结果数组中。
以下程序中使用的方法如下-
我们输入list(K)需要合并的数量。
一个节点类被初始化，负责创建链表的节点。
之后链表的节点按排序顺序初始化，链表的头部通过function(mergeLists)参数作为k
在函数内部，一个循环从第二个列表开始迭代，在循环内部迭代另一个循环，其中包含元素比较的所有实用程序。
第一个和第i个列表的头部被捕获并存储在变量中。
然后检查两个头部的较小头部元素和结果，然后将结果头部设置为最终列表的头部。
然后对列表的以下元素执行类似的过程，并根据它们的正确顺序比较和存储数据。
如果列表迭代到最后，则最后一个节点被设置为null，最终列表作为输出返回给用户。
示例
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Node {
int data;
Node next;
public Node(int data) {
this.data= data;
this.next= null;
}
}
public class testClass{
public static Node mergeLists(Node[] list, int k) {
PriorityQueue<Node> priorityQueue;
priorityQueue = new PriorityQueue<Node>(Comparator.comparingInt(a ->((Node) a).data));
priorityQueue.addAll(Arrays.asList(list).subList(0, k));
Node head = null, last = null;
while (!priorityQueue.isEmpty()) {
Node min = priorityQueue.poll();
if (head == null) {
head = last = min;
}
else {
last.next= min;
last = min;
}
if (min.next != null) {
priorityQueue.add(min.next);
}
}
return head;
}
public static void main(String[] s) {
int k = 3;
Node[] list = new Node[k];
list[0] = new Node(11);
list[0].next = new Node(15);
list[0].next.next = new Node(17);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(26);
list[1].next.next.next = new Node(39);
list[2] = new Node(4);
list[2].next = new Node(8);
list[2].next.next = new Node(10);
System.out.println("The merged list is-->");
Node head = mergeLists(list, k);
while (head != null) {
System.out.print(head.data + ">> ");
head = head.next;
}
System.out.print("null");
}
}输出结果如果我们运行上面的代码，它将生成以下输出
The merged list is--> 2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null