C语言合并两个顺序表代码实现

在C语言中，合并两个顺序表（也称为线性表，每个元素都有一个前驱和后继节点）可以使用递归或迭代的方式实现。这里提供一种简单的迭代法：

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 函数声明
Node* mergeLists(Node* list1, Node* list2);

// 合并两个列表函数
Node* mergeLists(Node* list1, Node* list2) {
    // 初始化临时指针和空链表
    if (!list1) return list2; // 如果list1为空，直接返回list2
    if (!list2) return list1; // 如果list2为空，直接返回list1

    // 创建一个新的头结点，并初始化
    Node* mergedList = (list1->data <= list2->data) ? list1 : list2;
    mergedList->next = NULL;

    // 遍历两个列表，选择较小的值添加到新链表
    while (list1 && list2) {
        if (list1->data <= list2->data) {
            mergedList->next = list1;
            list1 = list1->next;
        } else {
            mergedList->next = list2;
            list2 = list2->next;
        }
        mergedList = mergedList->next;
    }

    // 将剩余部分追加到新链表的末尾
    if (list1) mergedList->next = list1; // 如果list1还有剩余，追加
    if (list2) mergedList->next = list2; // 如果list2还有剩余，追加

    return mergedList;
}

int main() {
    // 创建示例链表
    Node* list1 = malloc(sizeof(Node));
    list1->data = 1;
    list1->next = malloc(sizeof(Node));
    list1->next->data = 3;
    list1->next->next = NULL;

    Node* list2 = malloc(sizeof(Node));
    list2->data = 2;
    list2->next = malloc(sizeof(Node));
    list2->next->data = 4;
    list2->next->next = NULL;

    // 合并并打印结果
    Node* merged = mergeLists(list1, list2);
    while (merged) {
        printf("%d ", merged->data);
        merged = merged->next;
    }
    free(list1);
    free(list2);
    return 0;
}