[C++知识库] 单链表合并（C语言）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 单链表合并（C语言） -> 正文阅读

[C++知识库]单链表合并（C语言）

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

// 合并两个有序链表

// 定义链表结构
typedef struct Node {
    int data;
    struct Node *next;
}Node,*LinkList;

// 初始化
LinkList initList() {
    LinkList L = (Node *) malloc (sizeof(Node));
    L->next = NULL;
    return L;
}

// 创建
void tailList (LinkList L) {
    Node *r,*s;
    int data;
    r = L;
    printf("输入(-1代表结束):");
    while(1) {
        scanf("%d",&data);
        if(data == -1) return;
        s = (Node *) malloc (sizeof(Node));
        s->data = data;
        r->next = s;
        r = s;
    }
}

// 打印
void printList (LinkList L) {
    Node *p;
    p = L;
    if(p->next == NULL) return;
    p = p->next;
    while(p) {
        printf("%d -> ",p->data);
        p = p->next;
    }
    printf("\n");
}

// 合并
// 这里的类型只能是 LinkList
LinkList mergeList(LinkList LA,LinkList LB) {
    Node *pa,*pb,*r;   // pa指向LA的第一个节点；pb指向LB的第一个节点；
    LinkList LC;    // r始终指向LC表尾；
    pa = LA->next;
    pb = LB->next;
    LC = LA;
    LC->next = NULL;
    r = LC;
    int i = 1;
    while (pa!=NULL && pb !=NULL) {
        if(pa->data <= pb->data) {
            printf("LA %d\n",pa->data);
            r->next = pa;
            r = pa;
            pa = pa->next;
        } else {
            printf("LB %d\n",pb->data);
            r->next = pb;
            r = pb;
            pb = pb->next;
        }
    }
    if(pa) {
        r->next = pa;
    } else {
        r->next = pb;
    }
    free(LA);
    printf("合并成功！\n");
}

// 主函数
int main() {
    LinkList LA,LB,LC;
    LA = initList();
    tailList(LA);
    printList(LA);
    LB = initList();
    tailList(LB);
    printList(LB);
    LC = mergeList(LA,LB);
    printList(LC);
    return 0;
}