C语言链式存储实现线性表合并：有序链表合并算法

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

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

// 建立链表函数
Node* createList(int n){
    Node* head = NULL;
    Node* tail = NULL;
    int i;
    for(i=0; i<n; i++){
        int data;
        printf("请输入第%d个元素的值：", i+1);
        scanf("%d", &data);
        
        // 创建新节点
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = data;
        newNode->next = NULL;
        
        if(head == NULL){
            head = newNode;
            tail = newNode;
        }else{
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

// 合并链表函数
Node* mergeLists(Node* list1, Node* list2){
    Node* head = NULL;
    Node* tail = NULL;
    
    while(list1 != NULL && list2 != NULL){
        if(list1->data <= list2->data){
            if(head == NULL){
                head = list1;
                tail = list1;
            }else{
                tail->next = list1;
                tail = list1;
            }
            list1 = list1->next;
        }else{
            if(head == NULL){
                head = list2;
                tail = list2;
            }else{
                tail->next = list2;
                tail = list2;
            }
            list2 = list2->next;
        }
    }
    
    if(list1 != NULL){
        tail->next = list1;
    }
    
    if(list2 != NULL){
        tail->next = list2;
    }
    
    return head;
}

// 输出链表中所有数据的函数
void printList(Node* head){
    Node* p = head;
    while(p != NULL){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main(){
    int n1, n2;
    printf("请输入第一个链表的元素个数：");
    scanf("%d", &n1);
    Node* list1 = createList(n1);
    
    printf("请输入第二个链表的元素个数：");
    scanf("%d", &n2);
    Node* list2 = createList(n2);
    
    Node* mergedList = mergeLists(list1, list2);
    
    printf("合并后的链表中所有数据为：");
    printList(mergedList);
    
    return 0;
}

使用示例： 请输入第一个链表的元素个数：3 请输入第1个元素的值：1 请输入第2个元素的值：3 请输入第3个元素的值：5 请输入第二个链表的元素个数：4 请输入第1个元素的值：2 请输入第2个元素的值：4 请输入第3个元素的值：6 请输入第4个元素的值：8 合并后的链表中所有数据为：1 2 3 4 5 6 8