JAVA解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 定義一個維護最終答案的 ans 連結清單
ListNode ans = null;
// 周遊 lists 中的所有連結清單
for (int i = 0; i < lists.length; ++i) {
// 其中兩兩合并
ans = mergeTwoLists(ans, lists[i]);
}
// 傳回最終合并完的答案
return ans;
}
// 實作兩兩合并的邏輯
public ListNode mergeTwoLists(ListNode a, ListNode b) {
// 隻要有一個連結清單為空則傳回另一個
if (a == null || b == null) {
return a != null ? a : b;
}
// 定義一個值為 0 的頭節點
ListNode head = new ListNode(0);
// 定義 tail 結點并讓頭節點指向它，定義兩個分别指向傳進的兩連結清單的指針節點
ListNode tail = head, aPtr = a, bPtr = b;
// 隻有連個指針節點不為空的時候進行周遊
while (aPtr != null && bPtr != null) {
// 兩兩值的比較并把 tail.next 指向較小的那個
if (aPtr.val < bPtr.val) {
tail.next = aPtr;
// 因為此時較小的已經存進去了，維護指針位置為原 aPtr 的下一個
aPtr = aPtr.next;
} else {
tail.next = bPtr;
// 因為此時較小的已經存進去了，維護指針位置為原 bPtr 的下一個
bPtr = bPtr.next;
}
// 因為 tail 已經更新是以要維護 tail 的位置為原 tail 的下一個
tail = tail.next;
}
// 若 aPtr == null 則證明 aPtr 到盡頭了，則接上 bPtr 即可，反之同理
tail.next = (aPtr != null ? aPtr : bPtr);
// 最後傳回
return head.next;
}
} 複制
題解分析
這道題合并多個有序連結清單，結合之前做過的合并兩個有序連結清單，這道題可以被拆成一個主線：周遊所有存在的連結清單，一個支路：用雙指針合并合并兩個有序連結清單。
首先，在主線中定義一個維護最終答案的 ans 連結清單，然後周遊 lists 中的所有連結清單，其中進入支路讓連結清單兩兩合并，合并完則傳回。
支路邏輯：傳進來的兩個連結清單隻要有一個連結清單為空則傳回另一個。定義一個虛拟的頭節點值為 0，定義 tail 結點并讓頭節點指向它，定義兩個分别指向傳進的兩連結清單的指針節點，隻有連個指針節點不為空的時候進行周遊。兩指針節點所在的節點值兩兩值的比較并把 tail.next 指向較小的那個，同時那個較小那個的節點已經被使用，是以要讓其指派為下一個節點，此時分的 taill 同理也要維護。
到此已經完成相同長度的合并了，若 aPtr == null 則證明 aPtr 到盡頭了，則接上 bPtr 即可，反之 aPtr != null 則并上 aPtr，因為上面的循環條件是 aPtr != null && bPtr != null，就是因為有一方為空才結束循環，但仍然還有一個連結清單剩下沒合并的部分，因為是有序的，是以直接合并即可。
做題感想
第一次接觸 hard 題，還是費了不少時間，一道題近一個鐘，還是感覺到了 hard 題的威力了，但是看評論這道題還是 hard 題裡邊算簡單的了，還要再接再厲。
leetcode原題：23. 合并K個升序連結清單