C/C++单链表基础三讲（三）：链表的归并与拆分

分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。

输入格式:

第一行输入M与N的值；
第二行依次输入M个有序的整数；
第三行依次输入N个有序的整数。

输出格式:

输出合并后的单链表所包含的M+N个有序的整数。

输入样例:
6 5
1 23 26 45 66 99
14 21 28 50 100
输出样例:
1 14 21 23 26 28 45 50 66 99 100

我们这次还是先给出完整代码，并标注注释供大家自学：

#include<bits/stdc++.h>
using namespace std;

// 定义链表节点结构
struct node{
    int data;       // 节点存储的数据
    node* next;     // 指向下一个节点的指针
};

/**
 * 创建一个包含n个节点的链表
 * @param n 链表的节点数量
 * @return 链表的头指针
 */
node* creat(int n){
    node* head = NULL;  // 头指针，初始为空
    node* tail = NULL;  // 尾指针，初始为空
    node* newnode;      // 临时指针，用于创建新节点
    
    // 循环创建n个节点
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;             // 输入节点数据
        
        newnode = new node;     // 动态分配新节点
        newnode->data = num;    // 给新节点赋值
        newnode->next = NULL;   // 新节点的next初始化为空
        
        // 如果是第一个节点（链表为空）
        if(head == NULL){
            head = newnode;     // 头指针指向第一个节点
            tail = newnode;     // 尾指针也指向第一个节点
        }
        else{
            tail->next = newnode;   // 尾节点的next指向新节点
            tail = newnode;         // 尾指针移动到新节点
        }
    }
    return head;  // 返回创建好的链表头指针
}

/**
 * 合并两个有序链表（假设均为升序）
 * @param list1 第一个有序链表的头指针
 * @param list2 第二个有序链表的头指针
 * @return 合并后的有序链表头指针
 */
node* mix(node* list1, node* list2){
    // 创建哑节点，简化边界条件处理（无需单独判断头节点）
    node* dummy = new node;
    dummy->data = 0;    // 哑节点数据无实际意义
    dummy->next = NULL;
    
    node* current = dummy;  // 当前指针，用于构建结果链表
    
    // 当两个链表都不为空时，循环比较节点值
    while (list1 != NULL && list2 != NULL){
        // 取较小值的节点接入结果链表
        if(list1->data <= list2->data){
            current->next = list1;  // 接入list1的当前节点
            list1 = list1->next;    // list1指针后移
        }
        else{
            current->next = list2;  // 接入list2的当前节点
            list2 = list2->next;    // list2指针后移
        }
        current = current->next;    // 当前指针后移
    }
    
    // 处理剩余节点（其中一个链表已遍历完毕）
    if(list1 != NULL){
        current->next = list1;  // 接入list1的剩余部分
    }
    if(list2 != NULL){
        current->next = list2;  // 接入list2的剩余部分
    }
    
    node* mix = dummy->next;   // 合并后的链表头指针（跳过哑节点）
    delete dummy;              // 释放哑节点内存
    return mix;                // 返回合并后的链表
}

/**
 * 打印链表所有节点数据
 * @param head 链表的头指针
 */
void print(node* head){
    node* current = head;  // 临时指针，用于遍历链表
    
    // 遍历链表直到尾节点
    while(current != NULL){
        cout << current->data;       // 打印当前节点数据
        
        // 最后一个节点后不打印空格
        if(current->next != NULL){
            cout << " ";
        }
        current = current->next;     // 指针后移
    }
    cout << endl;  // 打印结束后换行
}

int main(){
    int m, n;
    cin >> m >> n;  // 输入两个链表的长度
    
    // 创建两个链表
    node* list1 = creat(m);
    node* list2 = creat(n);
    
    // 合并两个有序链表
    node* mergedList = mix(list1, list2);
    
    // 打印合并后的链表
    print(mergedList);
    
    return 0;
}

为保持文章的简洁与可读性，同时提高大家的学习和复习能力，我们决定不再对前面讲过部分进行讲解，仅仅在下方给出每部分代码保持文章逻辑性。我们只详细讲解核心部分。

一、数据结构定义

// 定义链表节点结构
struct node{
    int data;       // 节点存储的数据
    int* next;      // 指向下一个节点的指针
};

二.链表创建

node* creat(int n){
    node* head = NULL;  // 头指针，初始为空
    node* tail = NULL;  // 尾指针，初始为空
    node* newnode;      // 临时指针，用于创建新节点
    
    // 循环创建n个节点
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;             // 输入节点数据
        
        newnode = new node;     // 动态分配新节点
        newnode->data = num;    // 给新节点赋值
        newnode->next = NULL;   // 新节点的next初始化为空
        
        // 如果是第一个节点（链表为空）
        if(head == NULL){
            head = newnode;     // 头指针指向第一个节点
            tail = newnode;     // 尾指针也指向第一个节点
        }
        else{
            tail->next = newnode;   // 尾节点的next指向新节点
            tail = newnode;         // 尾指针移动到新节点
        }
    }
    return head;  // 返回创建好的链表头指针
}

★三、链表合并函数(核心)

node* mix(node* list1, node* list2){
    // 创建临时节点，简化边界条件处理（无需单独判断头节点）
    node* dummy = new node;
    dummy->data = 0;    // 临时节点数据无实际意义
    dummy->next = NULL;
    
    node* current = dummy;  // 当前指针，用于构建结果链表
    
    // 当两个链表都不为空时，循环比较节点值
    while (list1 != NULL && list2 != NULL){
        // 取较小值的节点接入结果链表
        if(list1->data <= list2->data){
            current->next = list1;  // 接入list1的当前节点
            list1 = list1->next;    // list1指针后移
        }
        else{
            current->next = list2;  // 接入list2的当前节点
            list2 = list2->next;    // list2指针后移
        }
        current = current->next;    // 当前指针后移
    }
    
    // 处理剩余节点（其中一个链表已遍历完毕）
    if(list1 != NULL){
        current->next = list1;  // 接入list1的剩余部分
    }
    if(list2 != NULL){
        current->next = list2;  // 接入list2的剩余部分
    }
    
    node* mix = dummy->next;   // 合并后的链表头指针（跳过哑节点）
    delete dummy;              // 释放临时节点内存
    return mix;                // 返回合并后的链表
}

1,临时节点的创建

为了方便，临时节点以后统称哑节点

创建一个临时的「哑节点」作为合并链表的 “虚拟头”，避免处理链表为空时的边界问题（例如：当 list1 或 list2 为空时，无需单独判断合并后链表的头节点）。

哑节点的 data 字段无实际意义（赋值为 0 仅为初始化），核心价值在于其 next 指针 —— 用于指向合并后链表的真正头节点。

node* dummy = new node;
dummy->data = 0;    // 哑节点数据无实际意义
dummy->next = NULL;

2.初始化当前指针

node* current = dummy;  // 当前指针，用于构建结果链表

3.双指针遍历合并

while (list1 != NULL && list2 != NULL) {
    if (list1->data <= list2->data) {
        current->next = list1;  // 接入list1的当前节点
        list1 = list1->next;    // list1指针后移
    } else {
        current->next = list2;  // 接入list2的当前节点
        list2 = list2->next;    // list2指针后移
    }
    current = current->next;    // 当前指针后移
}

用 list1 和 list2 两个指针分别遍历两个输入链表，每次比较它们指向的节点值。
将值较小的节点通过 current->next 链接到合并链表的尾部（即 current 指向的节点后面）。
链接后，对应链表的指针（list1 或 list2）后移一位，同时 current 指针也后移一位，始终保持指向合并链表的尾部。
当 list1 或 list2 中有一个指针指向 NULL（即其中一个链表已遍历完毕）时，循环结束。

4. 处理剩余节点

if (list1 != NULL) {
    current->next = list1;  // 接入list1的剩余部分
}
if (list2 != NULL) {
    current->next = list2;  // 接入list2的剩余部分
}

当一个链表遍历完毕后，另一个链表可能仍有剩余节点（这些节点必然是有序的，且都大于已合并的所有节点），直接将剩余部分链接到合并链表的尾部。

5. 整理结果并返回

node* mix = dummy->next;   // 合并后的链表头指针（跳过哑节点）
delete dummy;              // 释放哑节点内存
return mix;                /

时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度，每个节点仅被遍历一次。
空间复杂度：O(1)，仅使用了常数个额外指针。

二、链表的拆分

输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。

输入格式:

第一行输入整数N;；
第二行依次输入N个整数。

输出格式:

第一行分别输出偶数链表与奇数链表的元素个数；
第二行依次输出偶数子链表的所有数据；
第三行依次输出奇数子链表的所有数据。

输入样例:
10
1 3 22 8 15 999 9 44 6 1001
输出样例:
4 6
22 8 44 6
1 3 15 999 9 1001

先给出完整代码：

#include<bits/stdc++.h>
using namespace std;

// 定义链表节点结构
struct node{
    int data;       // 节点存储的数据
    node* next;     // 指向下一个节点的指针
};

/**
 * 计算链表的长度
 * @param head 链表的头指针
 * @return 链表中节点的数量
 */
int getlen(node* head){
    int len = 0;
    node* current = head;  // 临时指针用于遍历链表
    
    // 遍历链表并计数
    while(current != NULL){
        len++;
        current = current->next;
    }
    return len;
}

/**
 * 打印链表所有节点数据
 * @param head 链表的头指针
 */
void print(node* head){
    node* current = head;  // 临时指针用于遍历链表
    
    // 遍历链表并打印每个节点的数据
    while(current != NULL){
        cout << current->data;
        
        // 最后一个节点后不打印空格
        if(current->next != NULL){
            cout << " ";
        }
        current = current->next;
    }
    cout << endl;  // 打印结束后换行
}

int main(){
    int n;
    cin >> n;  // 输入链表的长度
    
    // 创建原始链表
    node* head = NULL;    // 原始链表头指针
    node* tail = NULL;    // 原始链表尾指针
    node* newnode;        // 临时指针，用于创建新节点
    
    // 循环创建n个节点
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;             // 输入节点数据
        
        newnode = new node;     // 动态分配新节点
        newnode->data = num;    // 给新节点赋值
        newnode->next = NULL;   // 新节点的next初始化为空
        
        // 如果是第一个节点（链表为空）
        if(head == NULL){
            head = newnode;     // 头指针指向第一个节点
            tail = newnode;     // 尾指针也指向第一个节点
        }
        else{
            tail->next = newnode;   // 尾节点的next指向新节点
            tail = newnode;         // 尾指针移动到新节点
        }
    }
    
    // 定义偶数链表和奇数链表的头指针和尾指针
    node* ehead = NULL;  // 偶数链表头指针
    node* etail = NULL;  // 偶数链表尾指针
    node* ohead = NULL;  // 奇数链表头指针
    node* otail = NULL;  // 奇数链表尾指针
    
    node* current = head;  // 用于遍历原始链表的指针
    
    // 遍历原始链表，分割为偶数和奇数链表
    while(current != NULL){
        node* nextNode = current->next;  // 保存下一个节点的地址
        current->next = NULL;            // 断开当前节点与原链表的连接
        
        // 判断当前节点数据是否为偶数
        if(current->data % 2 == 0){
            // 添加到偶数链表
            if(ehead == NULL){
                ehead = current;
                etail = current;
            }
            else{
                etail->next = current;
                etail = current;
            }
        }
        else{
            // 添加到奇数链表
            if(ohead == NULL){
                ohead = current;
                otail = current;
            }
            else{
                otail->next = current;
                otail = current;
            }
        }
        
        current = nextNode;  // 移动到下一个节点
    }
    
    // 输出偶数链表和奇数链表的长度
    cout << getlen(ehead) << " " << getlen(ohead) << endl;
    
    // 打印偶数链表
    print(ehead);
    
    // 打印奇数链表
    print(ohead);
    
    return 0;
}

一、数据结构定义

// 定义链表节点结构
struct node{
    int data;       // 节点存储的数据
    node* next;     // 指向下一个节点的指针
};

二.链表长度计算函数

/**
 * 计算链表的长度
 * @param head 链表的头指针
 * @return 链表中节点的数量
 */
int getlen(node* head){
    int len = 0;
    node* current = head;  // 临时指针用于遍历链表
    
    // 遍历链表并计数
    while(current != NULL){
        len++;
        current = current->next;
    }
    return len;

三.链表打印函数

/**
 * 打印链表所有节点数据
 * @param head 链表的头指针
 */
void print(node* head){
    node* current = head;  // 临时指针用于遍历链表
    
    // 遍历链表并打印每个节点的数据
    while(current != NULL){
        cout << current->data;
        
        // 最后一个节点后不打印空格
        if(current->next != NULL){
            cout << " ";
        }
        current = current->next;
    }
    cout << endl;  // 打印结束后换行
}

四.原始链表创建

int n;
cin >> n;  // 输入链表的长度

// 创建原始链表
node* head = NULL;    // 原始链表头指针
node* tail = NULL;    // 原始链表尾指针
node* newnode;        // 临时指针，用于创建新节点

// 循环创建n个节点
for(int i = 0; i < n; i++){
    int num;
    cin >> num;             // 输入节点数据
    
    newnode = new node;     // 动态分配新节点
    newnode->data = num;    // 给新节点赋值
    newnode->next = NULL;   // 新节点的next初始化为空
    
    // 如果是第一个节点（链表为空）
    if(head == NULL){
        head = newnode;     // 头指针指向第一个节点
        tail = newnode;     // 尾指针也指向第一个节点
    }
    else{
        tail->next = newnode;   // 尾节点的next指向新节点
        tail = newnode;         // 尾指针移动到新节点
    }
}

五.奇偶链表拆分

// 定义偶数链表和奇数链表的头指针和尾指针
node* ehead = NULL;  // 偶数链表头指针
node* etail = NULL;  // 偶数链表尾指针
node* ohead = NULL;  // 奇数链表头指针
node* otail = NULL;  // 奇数链表尾指针

node* current = head;  // 用于遍历原始链表的指针

// 遍历原始链表，分割为偶数和奇数链表
while(current != NULL){
    node* nextNode = current->next;  // 保存下一个节点的地址
    current->next = NULL;            // 断开当前节点与原链表的连接
    
    // 判断当前节点数据是否为偶数
    if(current->data % 2 == 0){
        // 添加到偶数链表
        if(ehead == NULL){
            ehead = current;
            etail = current;
        }
        else{
            etail->next = current;
            etail = current;
        }
    }
    else{
        // 添加到奇数链表
        if(ohead == NULL){
            ohead = current;
            otail = current;
        }
        else{
            otail->next = current;
            otail = current;
        }
    }
    
    current = nextNode;  // 移动到下一个节点
}

六.奇偶链表拆分（核心）★

// 定义偶数链表和奇数链表的头指针和尾指针
node* ehead = NULL;  // 偶数链表头指针
node* etail = NULL;  // 偶数链表尾指针
node* ohead = NULL;  // 奇数链表头指针
node* otail = NULL;  // 奇数链表尾指针

node* current = head;  // 用于遍历原始链表的指针

// 遍历原始链表，分割为偶数和奇数链表
while(current != NULL){
    node* nextNode = current->next;  // 保存下一个节点的地址
    current->next = NULL;            // 断开当前节点与原链表的连接
    
    // 判断当前节点数据是否为偶数
    if(current->data % 2 == 0){
        // 添加到偶数链表
        if(ehead == NULL){
            ehead = current;
            etail = current;
        }
        else{
            etail->next = current;
            etail = current;
        }
    }
    else{
        // 添加到奇数链表
        if(ohead == NULL){
            ohead = current;
            otail = current;
        }
        else{
            otail->next = current;
            otail = current;
        }
    }
    
    current = nextNode;  // 移动到下一个节点
}

一、指针初始化

// 定义偶数链表和奇数链表的头指针和尾指针
node* ehead = NULL;  // 偶数链表头指针（指向偶数链表第一个节点）
node* etail = NULL;  // 偶数链表尾指针（指向偶数链表最后一个节点）
node* ohead = NULL;  // 奇数链表头指针（指向奇数链表第一个节点）
node* otail = NULL;  // 奇数链表尾指针（指向奇数链表最后一个节点）

node* current = head;  // 遍历指针：从原始链表的头节点开始逐个处理

核心目的：用「头指针 + 尾指针」的组合管理两个新链表（偶数链、奇数链）。
头指针（ehead/ohead）用于定位新链表的起点（后续打印、计算长度需用到）；尾指针（etail/otail）用于快速将新节点接入链表尾部（避免从头遍历找尾部，提升效率）。
初始状态：所有指针均为NULL，表示两个新链表初始为空；current从原始链表头部出发，准备遍历所有节点。

二、遍历循环：逐个处理原始链表节点

循环条件 while(current != NULL) 表示：只要还有未处理的节点，就继续循环（直到遍历完原始链表所有节点）。循环内部分为「保存后续节点」「断开原链接」「节点分类接入」「移动遍历指针」四步。

步骤 1：保存下一个节点地址（关键！避免遍历中断）

node* nextNode = current->next;  // 保存当前节点的下一个节点地址

为什么必须保存？
后续会执行 current->next = NULL（断开当前节点与原链表的连接），如果不提前用nextNode保存current->next的地址，遍历指针current会 “迷路”—— 再也找不到原始链表的下一个节点，导致遍历提前中断。
举例：若原始链表是 1→2→3，当current指向2时，nextNode会保存3的地址；即使2与3断开，后续仍能通过nextNode找到3。

步骤 2：断开当前节点与原链表的连接

current->next = NULL;  // 切断当前节点与原始链表的关联

核心作用：避免新链表之间产生 “交叉引用”。
若不断开，比如原始链表中2→3（2是偶数，3是奇数），当2接入偶数链表后，2的next仍指向3，会导致偶数链表末尾意外链接到奇数节点，破坏两个新链表的独立性（最终偶数链会包含3，不符合 “奇偶分割” 的需求）。

步骤 3：按奇偶性分类，将节点接入对应新链表

这是最核心的逻辑 —— 判断当前节点值的奇偶性，决定将其接入 “偶数链表” 还是 “奇数链表”，且两种链表的接入逻辑完全一致（仅指针变量不同）。

子情况 1：当前节点是偶数

if(ehead == NULL){  // 情况1：偶数链表为空（第一次添加偶数节点）
    ehead = current;  // 头指针指向当前节点（这是偶数链表第一个节点）
    etail = current;  // 尾指针也指向当前节点（此时链表只有一个节点，首尾重合）
}
else{  // 情况2：偶数链表已有节点（非第一次添加）
    etail->next = current;  // 让偶数链表的尾节点，指向当前节点（接入尾部）
    etail = current;        // 尾指针后移到当前节点（更新尾部位置）
}

逻辑拆解：
- 若偶数链表为空（ehead == NULL）：当前节点是第一个偶数节点，因此ehead（头）和etail（尾）同时指向它（链表只有一个节点时，首尾必然重合）。
- 若偶数链表已有节点：直接通过etail->next = current将当前节点 “挂” 在偶数链表的尾部，再把etail移到当前节点（确保下次添加时，etail仍指向尾部）。

子情况 2：当前节点是奇数

if(ohead == NULL){  // 情况1：奇数链表为空（第一次添加奇数节点）
    ohead = current;  // 头指针指向当前节点
    otail = current;  // 尾指针指向当前节点
}
else{  // 情况2：奇数链表已有节点
    otail->next = current;  // 接入奇数链表尾部
    otail = current;        // 更新尾指针
}

逻辑与偶数链表完全一致：仅将指针变量从ehead/etail换成ohead/otail，确保奇数节点正确接入奇数链表。

步骤 4：移动遍历指针，处理下一个节点

current = nextNode;  // 让遍历指针指向原始链表的下一个节点

作用：完成当前节点的处理后，通过之前保存的nextNode，让current指向原始链表的下一个节点，进入下一轮循环。
当current最终指向NULL时（原始链表遍历完毕），循环终止。

三、最终效果：两个独立的有序新链表

遍历结束后，原始链表的所有节点会被 “拆分” 到两个新链表中：

偶数链表：ehead指向第一个偶数节点，etail指向最后一个偶数节点，节点顺序与原始链表中偶数节点的顺序一致（如原始链1→2→3→4，偶数链为2→4）。
奇数链表：ohead指向第一个奇数节点，otail指向最后一个奇数节点，节点顺序与原始链表中奇数节点的顺序一致（如原始链1→2→3→4，奇数链为1→3）。
原始链表因所有节点被断开链接，已无实际意义（后续只需操作ehead和ohead即可）。

七.结果输出

// 输出偶数链表和奇数链表的长度
cout << getlen(ehead) << " " << getlen(ohead) << endl;

// 打印偶数链表
print(ehead);

// 打印奇数链表
print(ohead);

注：由于工作原因，该文章注释一部分参考AI,若有错误，欢迎指出纠正，谢谢。

三.总结

以上就是本讲的全部内容了，基础三讲也到此结束，也感谢大家的支持，因为工作的原因，本篇文章写的略有仓促，望大家理解。在接下来我会继续讲解链表的知识，同时我也会发布其他有关计算机科学内容，谢谢大家。

四.附录

例1

#include <stdio.h>
#include <stdlib.h>  // C语言动态内存分配（malloc/free）需包含此头文件

// 1. 定义链表节点结构体（C语言结构体无访问控制，直接定义成员）
struct Node {
    int data;       // 节点存储的整数数据
    struct Node* next;  // 指向下一个节点的指针（C语言需显式写struct Node）
};

// 2. 创建链表函数：接收节点数量n，返回链表头指针
struct Node* creat(int n) {
    struct Node* head = NULL;  // 链表头指针，初始为空
    struct Node* tail = NULL;  // 链表尾指针，初始为空
    struct Node* newNode;      // 临时指针，用于创建新节点

    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);  // C语言用scanf读取输入（需传地址）

        // C语言用malloc动态分配节点内存，需强制转换为struct Node*
        newNode = (struct Node*)malloc(sizeof(struct Node));
        // 检查内存分配是否成功（C语言需手动处理分配失败场景）
        if (newNode == NULL) {
            printf("内存分配失败！\n");
            exit(1);  // 分配失败则退出程序
        }

        newNode->data = num;  // 给新节点赋值
        newNode->next = NULL; // 新节点初始无后继，next设为NULL

        // 处理第一个节点（链表为空时）
        if (head == NULL) {
            head = newNode;  // 头指针指向第一个节点
            tail = newNode;  // 尾指针也指向第一个节点
        } else {
            tail->next = newNode;  // 尾节点的next指向新节点
            tail = newNode;        // 尾指针后移到新节点
        }
    }
    return head;  // 返回创建好的链表头指针
}

// 3. 合并两个有序链表函数：接收两个有序链表头指针，返回合并后的头指针
struct Node* mix(struct Node* list1, struct Node* list2) {
    // 创建哑节点（简化边界处理，C语言同样适用）
    struct Node* dummy = (struct Node*)malloc(sizeof(struct Node));
    if (dummy == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    dummy->data = 0;    // 哑节点数据无实际意义
    dummy->next = NULL;

    struct Node* current = dummy;  // 当前指针，用于构建结果链表

    // 双指针遍历：比较两个链表当前节点，接入较小值节点
    while (list1 != NULL && list2 != NULL) {
        if (list1->data <= list2->data) {
            current->next = list1;  // 接入list1的当前节点
            list1 = list1->next;    // list1指针后移
        } else {
            current->next = list2;  // 接入list2的当前节点
            list2 = list2->next;    // list2指针后移
        }
        current = current->next;    // 当前指针后移（始终指向结果链表尾部）
    }

    // 处理剩余节点（一个链表遍历完，直接接入另一个链表的剩余部分）
    if (list1 != NULL) {
        current->next = list1;
    }
    if (list2 != NULL) {
        current->next = list2;
    }

    // 取出合并后的真正头指针（跳过哑节点）
    struct Node* mergedHead = dummy->next;
    free(dummy);  // C语言用free释放哑节点内存（避免内存泄漏）
    return mergedHead;
}

// 4. 打印链表函数：接收链表头指针，遍历并打印所有节点
void print(struct Node* head) {
    struct Node* current = head;  // 临时指针用于遍历

    while (current != NULL) {
        printf("%d", current->data);
        // 最后一个节点后不打印空格
        if (current->next != NULL) {
            printf(" ");
        }
        current = current->next;  // 指针后移
    }
    printf("\n");  // 打印结束后换行
}

// 5. （可选）释放链表内存函数：避免程序结束后内存泄漏（C语言需手动释放）
void freeList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;       // 保存当前节点地址
        head = head->next; // 头指针后移
        free(temp);        // 释放当前节点内存
    }
}

// 主函数：程序入口，串联链表创建、合并、打印流程
int main() {
    int m, n;
    // C语言用scanf读取两个链表的长度（需传地址）
    scanf("%d %d", &m, &n);

    // 创建两个有序链表
    struct Node* list1 = creat(m);
    struct Node* list2 = creat(n);

    // 合并两个有序链表
    struct Node* mergedList = mix(list1, list2);

    // 打印合并后的链表
    print(mergedList);

    // 释放所有动态分配的内存（避免内存泄漏，养成良好习惯）
    freeList(mergedList);  // mergedList包含了list1和list2的所有节点，释放它即可

    return 0;
}

例2

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

// 定义链表节点结构体
struct node {
    int data;
    struct node* next;  // C语言中必须使用struct关键字
};

/**
 * 计算链表的长度
 * @param head 链表头指针
 * @return 链表节点数量
 */
int getlen(struct node* head) {
    int len = 0;
    struct node* current = head;  // 遍历指针
    while (current != NULL) {
        len++;
        current = current->next;
    }
    return len;
}

/**
 * 打印链表所有节点
 * @param head 链表头指针
 */
void print(struct node* head) {
    struct node* current = head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(" ");
        }
        current = current->next;
    }
    printf("\n");  // C语言使用printf输出
}

/**
 * 释放链表占用的内存
 * @param head 链表头指针
 */
void free_list(struct node* head) {
    struct node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);  // C语言使用free释放动态内存
    }
}

int main() {
    int n;
    scanf("%d", &n);  // C语言使用scanf输入

    // 创建原始链表
    struct node* head = NULL;
    struct node* tail = NULL;
    struct node* newnode;

    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);

        // C语言使用malloc分配内存，需要强制类型转换
        newnode = (struct node*)malloc(sizeof(struct node));
        if (newnode == NULL) {  // C语言需要检查内存分配是否成功
            printf("内存分配失败\n");
            return 1;
        }

        newnode->data = num;
        newnode->next = NULL;

        if (head == NULL) {
            head = newnode;
            tail = newnode;
        } else {
            tail->next = newnode;
            tail = newnode;
        }
    }

    // 定义偶数和奇数链表的头指针和尾指针
    struct node* ehead = NULL;
    struct node* etail = NULL;
    struct node* ohead = NULL;
    struct node* otail = NULL;

    struct node* current = head;

    // 遍历原始链表，分割为偶数和奇数链表
    while (current != NULL) {
        struct node* nextNode = current->next;  // 保存下一个节点地址
        current->next = NULL;                   // 断开当前节点与原链表的连接

        if (current->data % 2 == 0) {
            // 添加到偶数链表
            if (ehead == NULL) {
                ehead = current;
                etail = current;
            } else {
                etail->next = current;
                etail = current;
            }
        } else {
            // 添加到奇数链表
            if (ohead == NULL) {
                ohead = current;
                otail = current;
            } else {
                otail->next = current;
                otail = current;
            }
        }

        current = nextNode;  // 移动到下一个节点
    }

    // 输出结果
    printf("%d %d\n", getlen(ehead), getlen(ohead));
    print(ehead);
    print(ohead);

    // 释放内存，避免内存泄漏
    free_list(ehead);  // 释放偶数链表
    free_list(ohead);  // 释放奇数链表

    return 0;
}

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

程序员学 AI（八）：AI Agent 到底是什么？从回答问题到完成任务

AI Agent技术社区

22道AI Agent 工程师必会的面试题，别啥都不会就出去找工作

AI Agent技术社区

写给 TypeScript 工程师的 OpenClaw.NET 上手指南：用你熟悉的 TS 思维，跑起一个生产级 AI Agent

读代码层：TS 和 C# 本来就是「远房亲戚」——asyncawait??、接口、泛型、严格空检查，你的心智模型几乎无缝平移。真正要适应的只有两件事：类型是具名而非结构化的（多一句显式声明），以及 NativeAOT 下的「禁反射」约束。写扩展层：你甚至可以不怎么碰 C#——Node.js 插件桥意味着你的 TypeScript 插件就是一等公民，而且能在生产 aot 车道跑。内核给你 .NET