在 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 个列表的头部在变量中。
然后检查两个头部,寻找较小的头部元素,并将结果和结果头部设置为最终列表的头部。
然后对列表的以下元素执行类似的过程,并根据正确的顺序比较和存储数据。
如果列表迭代到最后,则最后一个节点设置为空,并将最终列表作为输出返回给用户。
示例
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