資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
