C++怎么合并兩個排序的鏈表

# C++怎么合并兩個排序的鏈表

## 引言

在數據結構與算法中，合并兩個已排序的鏈表是一個經典問題。該問題不僅考察對鏈表操作的理解，還涉及遞歸和迭代兩種解題思路。本文將詳細介紹在C++中如何高效實現這一操作，包括代碼實現、復雜度分析以及相關應用場景。

---

## 問題描述

給定兩個**非遞減順序排列**的鏈表`list1`和`list2`，要求將它們合并為一個新的**升序鏈表**并返回。新鏈表應通過拼接原鏈表的節點組成。

**示例輸入：**
```cpp
List1: 1 -> 3 -> 5
List2: 2 -> 4 -> 6

示例輸出：

1 -> 2 -> 3 -> 4 -> 5 -> 6

鏈表節點定義

首先，我們需要定義鏈表節點的結構。在C++中，通常如下表示：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

方法一：迭代法

算法思路

1. 創建一個虛擬頭節點（dummy node）作為新鏈表的起始點。
2. 使用指針curr跟蹤新鏈表的當前節點。
3. 比較兩個鏈表的當前節點值，將較小者接入新鏈表。
4. 移動被選中鏈表的指針到下一個節點。
5. 重復步驟3-4直到某一鏈表遍歷完畢。
6. 將剩余非空鏈表直接接入新鏈表末尾。

代碼實現

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0); // 虛擬頭節點
    ListNode* curr = &dummy;
    
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            curr->next = list1;
            list1 = list1->next;
        } else {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    
    // 處理剩余節點
    curr->next = list1 ? list1 : list2;
    return dummy.next;
}

復雜度分析

• 時間復雜度：O(n + m)，其中n和m分別為兩個鏈表的長度。
• 空間復雜度：O(1)，僅使用常數級別的額外空間。

方法二：遞歸法

算法思路

1. 遞歸基：如果任一鏈表為空，直接返回另一鏈表。
2. 比較兩個鏈表頭節點的值：
   • 若list1->val較小，則將list1->next與list2合并的結果接入list1。
   • 反之同理。
3. 返回當前較小節點作為新鏈表的頭節點。

代碼實現

ListNode* mergeTwoListsRecursive(ListNode* list1, ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1->val <= list2->val) {
        list1->next = mergeTwoListsRecursive(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoListsRecursive(list1, list2->next);
        return list2;
    }
}

復雜度分析

• 時間復雜度：O(n + m)，每次遞歸調用處理一個節點。
• 空間復雜度：O(n + m)，遞歸棧的深度最多為n+m。

方法對比

邊界條件處理

實際編碼時需考慮以下特殊情況： 1. 一個鏈表為空：直接返回另一個鏈表。 2. 兩個鏈表均為空：返回nullptr。 3. 鏈表有重復值：題目要求非遞減順序，重復值需保留。

應用場景

1. 歸并排序：合并鏈表是歸并排序的核心步驟。
2. 多路歸并：如合并K個有序鏈表的基礎操作。
3. 數據庫系統：合并多個有序結果集。

完整測試用例

#include <iostream>
using namespace std;

// 打印鏈表
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

// 測試代碼
int main() {
    // 構造鏈表1: 1->3->5
    ListNode a(1), b(3), c(5);
    a.next = &b; b.next = &c;
    
    // 構造鏈表2: 2->4->6
    ListNode d(2), e(4), f(6);
    d.next = &e; e.next = &f;
    
    cout << "List1: "; printList(&a);
    cout << "List2: "; printList(&d);
    
    // 合并鏈表
    ListNode* merged = mergeTwoLists(&a, &d);
    cout << "Merged: "; printList(merged);
    
    return 0;
}

輸出結果：

List1: 1 -> 3 -> 5 -> nullptr
List2: 2 -> 4 -> 6 -> nullptr
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nullptr

常見問題解答

Q1: 能否原地修改鏈表而不創建新節點？

A1: 可以。迭代法通過指針重定向實現原地合并，無需額外節點（虛擬頭節點除外）。

Q2: 如何處理降序鏈表？

A2: 若鏈表為降序，可先反轉鏈表再合并，或修改比較邏輯為list1->val >= list2->val。

Q3: 遞歸法的棧溢出風險？

A3: 當鏈表極長時（如數萬節點），遞歸可能導致棧溢出，此時應使用迭代法。

擴展思考

1. 合并K個有序鏈表：可通過分治策略，兩兩合并直至剩一個鏈表。
2. 雙向鏈表的合并：需額外處理prev指針，但核心邏輯相似。
3. 并行化優化：對于超大鏈表，可采用多線程分段合并。

總結

本文詳細講解了在C++中合并兩個有序鏈表的兩種方法： - 迭代法：推薦生產環境使用，空間效率高。 - 遞歸法：適合面試或小規模數據，代碼簡潔。

理解這一問題的解決方案，將為處理更復雜的鏈表操作（如環形鏈表檢測、重排序等）奠定堅實基礎。

參考文獻

1. 《算法導論》 - Thomas H. Cormen
2. LeetCode官方題解 - Merge Two Sorted Lists
3. C++標準庫文檔 - <list>實現原理

”`

注：實際字數約1800字，可根據需要增減示例或優化細節以達到精確字數要求。