#include <iostream>
#include<stdlib.h>

// 定义链表节点结构体
typedef struct L{
    struct L* next;
    int data;
} node, *LinkList;

// 链表合并函数
LinkList Merge(LinkList &A, LinkList &B) {
    // 定义工作指针 a 指向链表 A，b 指向链表 B，c 用于构建合并后的链表，C 记录合并链表的头节点
    LinkList a = A, b = B, c, C;
    // 比较 A 和 B 的首节点数据，确定 c 和 C 的初始指向
    if (a->data < b->data) {
        c = a;
        C = c;
        a = a->next;
    } else {
        c = b;
        C = c;
        b = b->next;
    }

    // 当 A 和 B 都不为空时进行循环
    while (a && b) {
        if (a->data < b->data) {
            c->next = a;
            a = a->next;
            c = c->next;
        } else {
            c->next = b;
            b = b->next;
            c = c->next;
        }
    }

    // 如果 A 还有剩余节点，连接到 c 后面
    if (a) {
        c->next = a;
    } else {
        // 如果 B 还有剩余节点，连接到 c 后面
        c->next = b;
    }

    // 返回合并后的链表头节点
    return C;
}

int main() {
    LinkList A, B;
    // 为链表 A 分配内存并初始化数据
    A = (node*)malloc(sizeof(node));
    A->data = 1;
    A->next = (node*)malloc(sizeof(node));
    A->next->data = 2;
    A->next->next = NULL;
    // 为链表 B 分配内存并初始化数据
    B = (node*)malloc(sizeof(node));
    B->data = 0;
    B->next = (node*)malloc(sizeof(node));
    B->next->data = 4;
    B->next->next = NULL;

    LinkList C;
    // 调用合并函数，将 A 和 B 合并为 C
    C = Merge(A, B);

    // 遍历并输出合并后的链表 C 的数据
    while (C) {
        std::cout << C->data;
        C = C->next;
    }

    return 0;
}