? ? ? ? 本篇博客將探討如何 “合并K個(gè)有序鏈表” 這一經(jīng)典問題。本文將從題目要求、解題思路、過程解析和相關(guān)知識點(diǎn)逐步展開，同時(shí)提供詳細(xì)注釋的代碼示例。

---

鏈表（Linked List）

? ? ? ? ?鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，由一系列節(jié)點(diǎn)（Node）通過指針鏈接在一起。與數(shù)組不同，鏈表中的元素在內(nèi)存中不需要連續(xù)存儲，每個(gè)節(jié)點(diǎn)包含兩部分：

• 數(shù)據(jù)部分：存儲節(jié)點(diǎn)的值或數(shù)據(jù)。
• 指針部分：存儲指向下一個(gè)節(jié)點(diǎn)的地址（單鏈表）或上一個(gè)和下一個(gè)節(jié)點(diǎn)的地址（雙向鏈表）。

? ? ? ? ?鏈表的類型主要有以下幾種：

• 單鏈表：每個(gè)節(jié)點(diǎn)只指向下一個(gè)節(jié)點(diǎn)。
• 雙向鏈表：每個(gè)節(jié)點(diǎn)既有指向下一個(gè)節(jié)點(diǎn)的指針，也有指向上一個(gè)節(jié)點(diǎn)的指針。
• 循環(huán)鏈表：鏈表的最后一個(gè)節(jié)點(diǎn)指向鏈表的頭節(jié)點(diǎn)，形成循環(huán)。

? ? ? ? ?鏈表的特點(diǎn)：

• 動態(tài)大小：可以根據(jù)需要?jiǎng)討B(tài)地增加或減少元素，無需預(yù)分配存儲空間。
• 插入/刪除效率高：在鏈表的任意位置進(jìn)行插入或刪除操作只需修改指針，不涉及大量元素的移動，效率較高。
• 隨機(jī)訪問效率低：由于鏈表不支持直接訪問任意位置的元素，需要通過遍歷來查找特定位置的節(jié)點(diǎn)。

? ? ? ? ?如下圖所示：

---

題目要求

? ? ? ? 給定 k 個(gè)有序的鏈表，要求將它們合并成一個(gè)有序鏈表，并返回最終的結(jié)果鏈表。

輸入

• 一個(gè)包含 k 個(gè)鏈表的數(shù)組，其中每個(gè)鏈表均已按升序排列。

輸出

• 一個(gè)合并后的鏈表，且鏈表內(nèi)元素按升序排列。

約束

1. k >= 1
2. 每個(gè)鏈表的長度可能不同，且長度總和不超過 10^5。
3. 鏈表節(jié)點(diǎn)的值范圍在 [-10^4, 10^4]。

---

解題思路

方法一：逐一合并

• 將所有鏈表兩兩合并。
• 時(shí)間復(fù)雜度為 O(k?n)，其中 n 為平均每個(gè)鏈表的長度。

方法二：使用最小堆（優(yōu)先隊(duì)列）

• 利用最小堆維護(hù)每個(gè)鏈表當(dāng)前節(jié)點(diǎn)的最小值，逐步提取并加入結(jié)果鏈表。
• 時(shí)間復(fù)雜度為 O(n?log?k)。

方法三：分治合并

• 將 k 個(gè)鏈表兩兩分組合并。
• 類似歸并排序，時(shí)間復(fù)雜度為 O(n?log?k)。

以下主要以 方法二：使用最小堆 和 方法三：分治合并 為例進(jìn)行解析。

---

過程解析

方法一：逐一合并

思路
? ? ? ? ?將第一個(gè)鏈表作為初始結(jié)果鏈表，然后逐個(gè)將剩余的鏈表與當(dāng)前結(jié)果鏈表進(jìn)行合并，直到所有鏈表合并完畢。

實(shí)現(xiàn)步驟

1. 初始化結(jié)果鏈表為第一個(gè)鏈表。
2. 遍歷鏈表數(shù)組，調(diào)用合并兩個(gè)鏈表的函數(shù)，將當(dāng)前鏈表與結(jié)果鏈表合并。
3. 返回最終結(jié)果鏈表。

優(yōu)點(diǎn)

• 實(shí)現(xiàn)簡單，邏輯清晰，適合入門時(shí)使用。

缺點(diǎn)

• 效率較低，尤其在鏈表數(shù)量較多或鏈表長度較大時(shí)。

---

方法二：使用最小堆

思路
? ? ? ? 利用最小堆（優(yōu)先隊(duì)列）維護(hù)鏈表當(dāng)前節(jié)點(diǎn)的最小值，每次從堆中提取最小值并將其加入結(jié)果鏈表，同時(shí)推進(jìn)對應(yīng)鏈表的指針。

實(shí)現(xiàn)步驟

1. 創(chuàng)建一個(gè)最小堆，將所有鏈表的頭節(jié)點(diǎn)加入堆中。
2. 反復(fù)提取堆頂最小值，將其加入結(jié)果鏈表。
3. 如果提取的節(jié)點(diǎn)有下一個(gè)節(jié)點(diǎn)，將下一個(gè)節(jié)點(diǎn)加入堆中。
4. 堆為空時(shí)，所有節(jié)點(diǎn)已處理完，返回結(jié)果鏈表。

優(yōu)點(diǎn)

• 在鏈表數(shù)量較多時(shí)表現(xiàn)優(yōu)秀。
• 保證結(jié)果鏈表的構(gòu)建是高效的。

缺點(diǎn)

• 實(shí)現(xiàn)稍復(fù)雜，需要熟悉堆的數(shù)據(jù)結(jié)構(gòu)。

---

方法三：分治合并

思路
? ? ? ? 通過分治思想，將鏈表分成兩組，遞歸地合并每組鏈表，直到最終只剩一個(gè)合并后的鏈表。

實(shí)現(xiàn)步驟

1. 將鏈表數(shù)組兩兩分組，遞歸合并每組鏈表。
2. 每次合并兩個(gè)鏈表使用合并兩個(gè)有序鏈表的邏輯。
3. 最終返回唯一的合并鏈表。

優(yōu)點(diǎn)

• 效率高，適合大規(guī)模鏈表數(shù)量。
• 思路清晰，類似歸并排序的合并邏輯。

缺點(diǎn)

• 實(shí)現(xiàn)需要遞歸，可能在棧深度受限的系統(tǒng)中受到限制。

---

三種方法的比較

方法	時(shí)間復(fù)雜度	空間復(fù)雜度	適用場景	實(shí)現(xiàn)復(fù)雜度
逐一合并	O(k?n)O(k \cdot n)O(k?n)	O(n)O(n)O(n)	鏈表數(shù)量較少時(shí)	簡單
使用最小堆	O(n?log?k)O(n \cdot \log k)O(n?logk)	O(k)O(k)O(k)	鏈表數(shù)量較多時(shí)	中等
分治合并	O(n?log?k)O(n \cdot \log k)O(n?logk)	O(log?k)O(\log k)O(logk)	大規(guī)模鏈表合并	中等

• 如果鏈表數(shù)量很少，逐一合并的實(shí)現(xiàn)最簡單，適合初學(xué)者練習(xí)。
• 如果鏈表數(shù)量較多且長度較短，最小堆法表現(xiàn)較優(yōu)。
• 如果鏈表數(shù)量和長度都較多，分治合并法綜合性能最好。

---

相關(guān)知識點(diǎn)

1. 鏈表操作

   • 基本操作：插入、刪除、遍歷。
   • 注意指針的動態(tài)分配與釋放。

2. 優(yōu)先隊(duì)列

   • C++ STL 中的std::priority_queue。
   • 自定義排序方式。

3. 分治策略

   • 遞歸與歸并思想。

---

示例代碼

C代碼實(shí)現(xiàn)：逐一合并

#include <stdio.h>  // 包含標(biāo)準(zhǔn)輸入輸出頭文件，提供 printf、scanf 等函數(shù)
#include <stdlib.h> // 包含動態(tài)內(nèi)存分配和其他實(shí)用功能函數(shù)，如 malloc 和 free// 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)
typedef struct ListNode {int val;               // 節(jié)點(diǎn)的值struct ListNode* next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} ListNode;// 合并兩個(gè)有序鏈表的函數(shù)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 如果 l1 為空，直接返回 l2if (!l1) return l2;// 如果 l2 為空，直接返回 l1if (!l2) return l1;// 比較兩個(gè)鏈表頭節(jié)點(diǎn)的值，遞歸合并較小值的后續(xù)節(jié)點(diǎn)if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2); // l1 較小，遞歸處理 l1->nextreturn l1;                              // 返回 l1 作為新的頭節(jié)點(diǎn)} else {l2->next = mergeTwoLists(l1, l2->next); // l2 較小，遞歸處理 l2->nextreturn l2;                              // 返回 l2 作為新的頭節(jié)點(diǎn)}
}// 合并 K 個(gè)有序鏈表的函數(shù)
ListNode* mergeKLists(ListNode** lists, int k) {// 如果鏈表數(shù)組為空，直接返回 NULLif (k == 0) return NULL;// 初始化結(jié)果鏈表為第一個(gè)鏈表ListNode* mergedList = lists[0];// 遍歷鏈表數(shù)組，從第二個(gè)鏈表開始逐一合并for (int i = 1; i < k; ++i) {mergedList = mergeTwoLists(mergedList, lists[i]); // 合并當(dāng)前結(jié)果鏈表和下一個(gè)鏈表}// 返回最終合并完成的結(jié)果鏈表return mergedList;
}// 輔助函數(shù)：打印鏈表
void printList(ListNode* head) {// 遍歷鏈表，打印每個(gè)節(jié)點(diǎn)的值while (head) {printf("%d -> ", head->val); // 輸出當(dāng)前節(jié)點(diǎn)的值head = head->next;          // 移動到下一個(gè)節(jié)點(diǎn)}printf("NULL\n"); // 鏈表結(jié)束后打印 NULL
}// 輔助函數(shù)：創(chuàng)建鏈表節(jié)點(diǎn)
ListNode* createNode(int val) {// 動態(tài)分配內(nèi)存為新節(jié)點(diǎn)ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->val = val;   // 設(shè)置節(jié)點(diǎn)值node->next = NULL; // 初始化下一個(gè)節(jié)點(diǎn)指針為空return node;       // 返回新節(jié)點(diǎn)的指針
}// 主函數(shù)測試
int main() 
{// 構(gòu)建測試鏈表 1：1 -> 4 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 構(gòu)建測試鏈表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 構(gòu)建測試鏈表 3：2 -> 6ListNode* list3 = createNode(2);list3->next = createNode(6);// 創(chuàng)建鏈表數(shù)組存儲所有鏈表ListNode* lists[] = {list1, list2, list3};// 合并鏈表ListNode* mergedList = mergeKLists(lists, 3);// 輸出結(jié)果鏈表printf("Merged List: ");printList(mergedList);return 0; // 程序正常結(jié)束
}

C代碼實(shí)現(xiàn)：最小堆解法

?示例代碼

#include <stdio.h>  // 包含標(biāo)準(zhǔn)輸入輸出頭文件
#include <stdlib.h> // 包含動態(tài)內(nèi)存分配函數(shù)// 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)
typedef struct ListNode {int val;               // 節(jié)點(diǎn)值struct ListNode* next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} ListNode;// 定義小頂堆結(jié)構(gòu)
typedef struct MinHeap {ListNode** array; // 存儲鏈表節(jié)點(diǎn)的指針數(shù)組int size;         // 當(dāng)前堆的大小int capacity;     // 堆的容量
} MinHeap;// 創(chuàng)建小頂堆
MinHeap* createMinHeap(int capacity) {// 分配堆結(jié)構(gòu)和數(shù)組的內(nèi)存MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));heap->array = (ListNode**)malloc(sizeof(ListNode*) * capacity);heap->size = 0;       // 初始化堆的大小為 0heap->capacity = capacity; // 設(shè)置堆容量return heap;          // 返回堆的指針
}// 交換兩個(gè)鏈表節(jié)點(diǎn)的指針
void swap(ListNode** a, ListNode** b) {ListNode* temp = *a;*a = *b;*b = temp;
}// 堆化調(diào)整函數(shù)（維護(hù)堆的性質(zhì)）
void heapify(MinHeap* heap, int i) {int smallest = i;            // 假設(shè)當(dāng)前節(jié)點(diǎn)為最小值int left = 2 * i + 1;        // 左子節(jié)點(diǎn)索引int right = 2 * i + 2;       // 右子節(jié)點(diǎn)索引// 如果左子節(jié)點(diǎn)更小，更新最小值索引if (left < heap->size && heap->array[left]->val < heap->array[smallest]->val)smallest = left;// 如果右子節(jié)點(diǎn)更小，更新最小值索引if (right < heap->size && heap->array[right]->val < heap->array[smallest]->val)smallest = right;// 如果最小值不是當(dāng)前節(jié)點(diǎn)，交換并遞歸調(diào)整if (smallest != i) {swap(&heap->array[i], &heap->array[smallest]);heapify(heap, smallest);}
}// 將節(jié)點(diǎn)插入到堆中
void insertHeap(MinHeap* heap, ListNode* node) {// 將新節(jié)點(diǎn)放在堆末尾heap->array[heap->size++] = node;int i = heap->size - 1; // 當(dāng)前節(jié)點(diǎn)的索引// 向上調(diào)整節(jié)點(diǎn)位置以維護(hù)堆的性質(zhì)while (i && heap->array[(i - 1) / 2]->val > heap->array[i]->val) {swap(&heap->array[i], &heap->array[(i - 1) / 2]);i = (i - 1) / 2; // 移動到父節(jié)點(diǎn)}
}// 從堆中提取最小值節(jié)點(diǎn)
ListNode* extractMin(MinHeap* heap) {if (heap->size == 0) return NULL; // 堆為空時(shí)返回 NULL// 獲取堆頂最小值ListNode* root = heap->array[0];// 將堆末尾的節(jié)點(diǎn)移到堆頂heap->array[0] = heap->array[--heap->size];// 調(diào)整堆以恢復(fù)堆的性質(zhì)heapify(heap, 0);return root; // 返回提取的最小值節(jié)點(diǎn)
}// 合并 K 個(gè)有序鏈表的函數(shù)
ListNode* mergeKLists(ListNode** lists, int k) {// 創(chuàng)建最小堆MinHeap* heap = createMinHeap(k);// 將每個(gè)鏈表的頭節(jié)點(diǎn)加入堆中for (int i = 0; i < k; ++i) {if (lists[i]) insertHeap(heap, lists[i]);}// 創(chuàng)建結(jié)果鏈表的啞節(jié)點(diǎn)（dummy 節(jié)點(diǎn)）ListNode dummy;ListNode* tail = &dummy; // 結(jié)果鏈表的尾部指針dummy.next = NULL;// 從堆中逐一提取最小值節(jié)點(diǎn)并加入結(jié)果鏈表while (heap->size > 0) {// 提取堆中的最小值節(jié)點(diǎn)ListNode* minNode = extractMin(heap);// 將最小值節(jié)點(diǎn)連接到結(jié)果鏈表tail->next = minNode;tail = tail->next; // 更新尾部指針// 如果提取的節(jié)點(diǎn)還有下一個(gè)節(jié)點(diǎn)，將其加入堆中if (minNode->next) insertHeap(heap, minNode->next);}// 釋放堆的內(nèi)存free(heap->array);free(heap);return dummy.next; // 返回結(jié)果鏈表的頭節(jié)點(diǎn)
}// 輔助函數(shù)：打印鏈表
void printList(ListNode* head) {while (head) {printf("%d -> ", head->val); // 打印節(jié)點(diǎn)值head = head->next;          // 移動到下一個(gè)節(jié)點(diǎn)}printf("NULL\n"); // 鏈表結(jié)束
}// 輔助函數(shù)：創(chuàng)建鏈表節(jié)點(diǎn)
ListNode* createNode(int val) {ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配內(nèi)存node->val = val;   // 設(shè)置節(jié)點(diǎn)值node->next = NULL; // 初始化下一個(gè)指針return node;
}// 主函數(shù)測試
int main() 
{// 構(gòu)建測試鏈表 1：1 -> 4 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 構(gòu)建測試鏈表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 構(gòu)建測試鏈表 3：2 -> 6ListNode* list3 = createNode(2);list3->next = createNode(6);// 創(chuàng)建鏈表數(shù)組ListNode* lists[] = {list1, list2, list3};// 合并鏈表ListNode* mergedList = mergeKLists(lists, 3);// 輸出結(jié)果鏈表printf("Merged List: ");printList(mergedList);return 0; // 程序結(jié)束
}

補(bǔ)充

小頂堆性質(zhì)

? ? ? ? ? 小頂堆（Min-Heap） 是一種完全二叉樹，它具有以下性質(zhì)：

堆的結(jié)構(gòu)性質(zhì)：

• 小頂堆是一棵完全二叉樹，即樹是從左到右逐層填滿的，只有最后一層可能不滿，但節(jié)點(diǎn)必須從左向右連續(xù)排列。

堆的值性質(zhì)：

• 每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。
• 即：對于任意節(jié)點(diǎn) i，有：

A[i] ≤ A[2i+1](左子節(jié)點(diǎn)值)
A[i] ≤ A[2i+2](右子節(jié)點(diǎn)值)

? ? ? ? 由于這兩個(gè)性質(zhì)，堆的最小值始終存儲在根節(jié)點(diǎn)（即數(shù)組的第一個(gè)位置）。

? ? ? ? 數(shù)組表示：堆可以使用數(shù)組表示，將完全二叉樹的節(jié)點(diǎn)按層序遍歷的順序存儲：

索引:     0   1   2   3   4   5
值:       10  15  20  30  40  25

在數(shù)組中，可以通過以下規(guī)則找到父子節(jié)點(diǎn)的關(guān)系：

• 父節(jié)點(diǎn)索引： parent(i) = (i?1) / 2
• 左子節(jié)點(diǎn)索引： left(i) = 2i+1
• 右子節(jié)點(diǎn)索引： right(i) = 2i+2

示例：一個(gè)滿足小頂堆性質(zhì)的完全二叉樹：

        10/  \15   20/ \   /30 40 25

heapify 函數(shù)的作用

void heapify(MinHeap* heap, int i);

• i: 要調(diào)整的節(jié)點(diǎn)在堆數(shù)組中的索引。
• heap: 表示一個(gè)小頂堆，包含節(jié)點(diǎn)數(shù)組和堆的大小。

? ? ? ? ?heapify 函數(shù)是小頂堆的調(diào)整函數(shù)，用來維護(hù)堆的性質(zhì)（即每個(gè)節(jié)點(diǎn)的值都不大于其子節(jié)點(diǎn)的值）。它的作用是：

• 從索引 i?開始，將子樹調(diào)整為滿足小頂堆性質(zhì)。
• 如果某節(jié)點(diǎn)不滿足小頂堆性質(zhì)，則通過交換該節(jié)點(diǎn)和其較小子節(jié)點(diǎn)的值，并遞歸調(diào)整子樹，直到整個(gè)堆滿足小頂堆性質(zhì)。

實(shí)現(xiàn)邏輯

1. 假設(shè)當(dāng)前節(jié)點(diǎn)的值是最小的（設(shè)索引為 smallest）。
2. 比較當(dāng)前節(jié)點(diǎn)和其左、右子節(jié)點(diǎn)的值：
   • 如果左子節(jié)點(diǎn)更小，更新 smallest為左子節(jié)點(diǎn)索引。
   • 如果右子節(jié)點(diǎn)更小，更新 smallest為右子節(jié)點(diǎn)索引。
3. 如果 smallest 發(fā)生變化（當(dāng)前節(jié)點(diǎn)不是最小值），交換當(dāng)前節(jié)點(diǎn)和 smallest的值。
4. 遞歸調(diào)用 heapify，確保調(diào)整后的子樹也滿足小頂堆性質(zhì)。

示例說明

? ? ? ? 假設(shè)有以下堆數(shù)組，表示一個(gè)不完全滿足小頂堆性質(zhì)的堆：

索引:      0   1   2   3   4   5
值:        40  15  20  30  10  25

? ? ? ? ?對應(yīng)的堆結(jié)構(gòu)：

        40/  \15   20/ \   /30  10 25

調(diào)用 heapify(heap, 0)

1. 當(dāng)前節(jié)點(diǎn)： 40（索引 0）。
2. 左子節(jié)點(diǎn)：15（索引 1）。
3. 右子節(jié)點(diǎn)：20（索引 2）。
4. 最小值為左子節(jié)點(diǎn) 15，交換 40 和 15。

調(diào)整后堆數(shù)組：

索引:      0   1   2   3   4   5
值:        15  40  20  30  10  25

對應(yīng)堆結(jié)構(gòu)：

        15/  \40   20/ \   /30  10 25

遞歸調(diào)用 heapify(heap, 1)：

• 當(dāng)前節(jié)點(diǎn)：40（索引 1）。
• 左子節(jié)點(diǎn)：30（索引 3）。
• 右子節(jié)點(diǎn)：10（索引 4）。
• 最小值為右子節(jié)點(diǎn) 10，交換 40 和 10。

調(diào)整后堆數(shù)組：

索引:      0   1   2   3   4   5
值:        15  10  20  30  40  25

對應(yīng)堆結(jié)構(gòu)：

        15/  \10   20/ \   /30  40 25

heapify(heap, 4) 不再需要調(diào)整，因?yàn)?40 沒有子節(jié)點(diǎn)。

最終堆數(shù)組：

索引:      0   1   2   3   4   5
值:        15  10  20  30  40  25

?最終堆結(jié)構(gòu)：

        15/  \10   20/ \   /30  40 25

C++代碼實(shí)現(xiàn)：分治解法

#include <stdio.h>  // 包含標(biāo)準(zhǔn)輸入輸出頭文件
#include <stdlib.h> // 包含動態(tài)內(nèi)存分配函數(shù)// 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)
typedef struct ListNode {int val;               // 節(jié)點(diǎn)值struct ListNode* next; // 指向下一個(gè)節(jié)點(diǎn)的指針
} ListNode;// 合并兩個(gè)有序鏈表的函數(shù)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {// 如果 l1 為空，直接返回 l2if (!l1) return l2;// 如果 l2 為空，直接返回 l1if (!l2) return l1;// 比較兩個(gè)鏈表的頭節(jié)點(diǎn)，選擇較小值作為合并后鏈表的頭節(jié)點(diǎn)if (l1->val < l2->val) {l1->next = mergeTwoLists(l1->next, l2); // 遞歸處理 l1->next 和 l2return l1;                              // 返回 l1 作為當(dāng)前鏈表頭} else {l2->next = mergeTwoLists(l1, l2->next); // 遞歸處理 l1 和 l2->nextreturn l2;                              // 返回 l2 作為當(dāng)前鏈表頭}
}// 分治法合并 K 個(gè)有序鏈表
ListNode* mergeKListsDivideAndConquer(ListNode** lists, int left, int right) {// 如果左邊界等于右邊界，表示只剩下一個(gè)鏈表if (left == right) return lists[left];// 如果左邊界大于右邊界，返回 NULLif (left > right) return NULL;// 計(jì)算中間位置int mid = left + (right - left) / 2;// 遞歸地合并左半部分鏈表ListNode* l1 = mergeKListsDivideAndConquer(lists, left, mid);// 遞歸地合并右半部分鏈表ListNode* l2 = mergeKListsDivideAndConquer(lists, mid + 1, right);// 合并左右兩部分鏈表return mergeTwoLists(l1, l2);
}// 主函數(shù)入口，用于調(diào)用分治法合并鏈表
ListNode* mergeKLists(ListNode** lists, int k) {// 如果鏈表數(shù)組為空，直接返回 NULLif (k == 0) return NULL;// 調(diào)用分治法進(jìn)行合并return mergeKListsDivideAndConquer(lists, 0, k - 1);
}// 輔助函數(shù)：打印鏈表
void printList(ListNode* head) {while (head) {printf("%d -> ", head->val); // 打印當(dāng)前節(jié)點(diǎn)的值head = head->next;          // 移動到下一個(gè)節(jié)點(diǎn)}printf("NULL\n"); // 鏈表結(jié)束
}// 輔助函數(shù)：創(chuàng)建鏈表節(jié)點(diǎn)
ListNode* createNode(int val) {ListNode* node = (ListNode*)malloc(sizeof(ListNode)); // 分配內(nèi)存node->val = val;   // 設(shè)置節(jié)點(diǎn)值node->next = NULL; // 初始化指針return node;       // 返回新節(jié)點(diǎn)
}// 主函數(shù)測試
int main() 
{// 構(gòu)建測試鏈表 1：1 -> 4 -> 5ListNode* list1 = createNode(1);list1->next = createNode(4);list1->next->next = createNode(5);// 構(gòu)建測試鏈表 2：1 -> 3 -> 4ListNode* list2 = createNode(1);list2->next = createNode(3);list2->next->next = createNode(4);// 構(gòu)建測試鏈表 3：2 -> 6ListNode* list3 = createNode(2);list3->next = createNode(6);// 創(chuàng)建鏈表數(shù)組ListNode* lists[] = {list1, list2, list3};// 調(diào)用分治法合并鏈表ListNode* mergedList = mergeKLists(lists, 3);// 打印結(jié)果鏈表printf("Merged List: ");printList(mergedList);return 0; // 程序正常結(jié)束
}