11. C 语言中链表的合并操作详解

# 1. 链表简介

### 1.1 什么是链表
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

### 1.2 链表的特点
- 链表可以动态地分配内存空间，大小不固定；
- 插入和删除节点操作效率高，时间复杂度为O(1)；
- 链表不需要连续的内存空间，灵活性高。

### 1.3 链表的分类
1. 单向链表：每个节点只有一个指针，指向下一个节点。
2. 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
3. 循环链表：尾节点指向头节点，形成一个环形结构。

# 2. 链表操作基础

在本章中，我们将介绍链表的基本操作，包括创建链表、遍历链表、插入节点和删除节点等。链表是一种重要的数据结构，掌握这些基本操作对于后续学习链表合并等更高级操作非常重要。

### 2.1 创建链表

在创建链表时，我们需要定义节点结构体，并编写相应的函数来实现链表的创建和初始化。

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

int main() {
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    head->next = second;
    return 0;
}

**代码总结：** 以上代码演示了如何创建一个简单的链表结构，包括定义节点结构体和创建节点的函数。

### 2.2 遍历链表

遍历链表是指按顺序访问链表中的每个节点，可以通过循环实现。

void traverseLinkedList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建链表
    struct Node* head = createNode(1);
    struct Node* second = createNode(2);
    head->next = second;
    // 遍历链表
    traverseLinkedList(head);
    return 0;
}

**代码总结：** 通过循环遍历链表中的每个节点，并输出节点的数据值，直到遍历到链表的末尾。

接下来，我们将介绍链表操作基础的插入节点和删除节点操作。

# 3. 链表合并的概念

### 3.1 什么是链表合并
链表合并是指将两个有序链表合并成一个新的有序链表的过程。合并后的链表仍然保持原有的有序性。

### 3.2 链表合并的应用场景
链表合并常见于各类排序算法、搜索算法等场景中，例如归并排序、合并两个有序链表等。

### 链表合并示意图
下面是链表合并的示意图：

graph LR
    A((链表1)) --> B((链表2))
    B --> C((合并))
    C --> D((新链表))

## 代码示例
下面以Python语言示例，演示如何合并两个有序链表：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    # Create a dummy node as the head of the merged list
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    # Handle the remaining nodes
    if l1:
        current.next = l1
    else:
        current.next = l2
    return dummy.next

### 代码解释
- 首先定义了一个链表节点类ListNode
- 然后定义了一个mergeTwoLists函数，用于合并两个有序链表
- 使用dummy节点作为新链表的头部，同时使用current节点来遍历新链表
- 遍历l1和l2，比较节点值大小，将较小值的节点接入新链表
- 处理剩余节点，将剩余的节点接入新链表
- 返回合并后的新链表的头部

这样，我们就完成了利用迭代法合并两个有序链表的操作。

# 4. 链表合并的方法

在这一章节中，我们将介绍两种常用的方法来实现链表的合并操作，分别是迭代法和递归法。通过这两种方法的讲解，读者可以更深入地理解链表的合