題目描述
有如下有序鏈表 n1, n2：
1 -> 5 -> 9
1 -> 3 -> 6 -> 10
要求對鏈表進行合并，合并后的新鏈表依然有序：
1 -> 1 -> 3 -> 5 -> 6 -> 9 -> 10
題目決議
由于鏈表是有序的，因此在遍歷 n1, n2 的程序中，只需比較出兩個鏈表較小的節點，將該節點追加在新鏈表末尾即可，比較步驟分解如下：
- 創建一個空節點，表示新鏈表頭部，創建兩個參考，記為 head, tmp，均指向頭節點，head 用于回傳新鏈表，tmp 用于追加鏈表節點，
- 比較 n1, n2， n1 <= n2 （注意相等的情況），將 n1 追加在 head 末尾，n1 指向的當前節點不再參與后續比較，移動 n1, tmp，
- n2 < n1，追加 n2，移動 n2, tmp，
- n2 < n1，追加 n2，移動 n2, tmp，
- n1 <= n2，追加 n1，移動 n1, tmp，
- n2 < n1，追加 n2，移動 n2, tmp，
- n1 <= n2，追加 n1，移動 n1, tmp，
- 此時 n1 指向了空，將 n2 直接追加在 tmp 后面即可，至此合并結束，tmp 無需再移動，head.next 就是新鏈表的頭節點，
經過上述分析，可以得出解題步驟：
- 遍歷 n1, n2 鏈表，將值較小的節點追加在 tmp 節點后，移動 tmp 和較小值節點參考；
- 當 n1, n2 任意一方遍歷到空時，停止遍歷，將非空的一方追加在 tmp 后；
- 回傳 head 的下一個節點，
代碼實作
代碼實作如下：
/**
* 合并兩個有序鏈表，合并后的鏈表依然有序
*
* @param n1
* @param n2
* @return
*/
public static Node mergeSortedLinkedList(Node n1, Node n2) {
if (n1 == null && n2 == null) {
throw new RuntimeException("n1, n2 不能都為空");
}
if (n1 == null) {
return n2;
}
if (n2 == null) {
return n1;
}
//創建空的頭節點
Node head = new Node();
//創建臨時參考，用于追加節點
Node tmp = head;
do {
if (n1.num <= n2.num) {
//若 n1 小，則追加 n1，同時 n1 后移
tmp.next = n1;
n1 = n1.next;
} else {
//若 n2 小，則追加 n2，同時 n2 后移
tmp.next = n2;
n2 = n2.next;
}
//追加節點后，tmp 后移
tmp = tmp.next;
//當 n1, n2 均不為空時，繼續比較
} while (n1 != null && n2 != null);
if (n1 == null) {
//若 n1 為空，則追加 n2 整體
tmp.next = n2;
} else {
//若 n2 為空，則追加 n1 整體
tmp.next = n1;
}
//置空 tmp，便于垃圾回收
tmp = null;
//回傳新鏈表的起始參考
return head.next;
}
結果驗證
有如下測驗代碼：
// 創建鏈表：1 -> 5 -> 9
Node n1 = new Node(1);
n1.next = new Node(5);
n1.next.next = new Node(9);
//創建鏈表：1 -> 3 -> 6 -> 10
Node n2 = new Node(1);
n2.next = new Node(3);
n2.next.next = new Node(6);
n2.next.next.next = new Node(10);
//合并有序鏈表 n1, n2
Node head = mergeSortedLinkedList(n1, n2);
System.out.println("n1: " + show(n1));
System.out.println("n2: " + show(n2));
System.out.println("合并后的鏈表：" + show(head));
輸出如下：
n1: [Node{num=1}, Node{num=5}, Node{num=9}]
n2: [Node{num=1}, Node{num=3}, Node{num=6}, Node{num=10}]
合并后的鏈表： [Node{num=1}, Node{num=1}, Node{num=3}, Node{num=5}, Node{num=6}, Node{num=9}, Node{num=10}]
結果如預期，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353165.html
標籤：其他
上一篇：漢文博士 0.6 測驗版即將發布