数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Java 中合并 K 个排序链表
给定 K 个大小不同的已排序链表，我们需要将这些链表合并成一个结果链表，使得结果链表也是排序的，并将结果数组作为输出打印给用户。
让我们通过例子来理解：
输入 -
int k = 3;
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);
输出 - 合并后的列表是-->
2>> 3>> 4>> 8>> 10>> 11>> 15>> 17>> 26>> 39>> null
解释 - 给定 K 个已排序的链表。合并过程包括使用 Java 比较器函数比较链表的头节点，并将它们合并到结果数组中。
输入 -
int k = 2;
list[0] = new Node(1);
list[0].next = new Node(4);
list[0].next.next = new Node(5);
list[1] = new Node(2);
list[1].next = new Node(3);
list[1].next.next = new Node(6);
list[1].next.next.next = new Node(8);
输出 - 合并后的列表是-->
1>> 2>> 3>> 4>> 5>> 6>> 8>> null
解释 - 给定 K 个已排序的链表。合并过程包括使用 Java 比较器函数比较链表的头节点，并将它们合并到结果数组中。
下面程序中使用的方案如下 -
我们输入需要合并的列表数量 (K)。
初始化一个节点类，用于创建链表的节点。
之后，以排序的顺序初始化链表的节点，并将链表的头节点作为参数传递给函数 (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
675 次浏览
