链表

typedef struct Node {
    int data;
    // 指向下个节点指针
    struct Node *next;
} Node;

Node* InitHead() {
    NodeList head = (NodeList)malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

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

typedef struct Lnode {
    int data;
    struct Lnode *next;
} Lnode, *Linklist;

// 初始化
Linklist InitHeadNode(Linklist &head) {
    head = (Linklist)malloc(sizeof(Lnode));
    head->next = NULL;
    return head;
}

// 后插法建立链表
Linklist CreateNodeList(Linklist &head, int n) {
    head->next = NULL;
    Linklist p;
    Linklist r = head;
    for (int i = 0; i < n; i++) {
        p = (Linklist)malloc(sizeof(Lnode));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
    return head;
}

void MergeNode(Linklist &head1, Linklist &head2, Linklist &head3) {
    Linklist p1, p2, p3;
    p1 = head1->next;
    p2 = head2->next;

    head3 = head1;
    p3 = head3;
    // 两个表均为到末尾, 则依次摘取
    while (p1 && p2) {
        // 摘取第一条链上的点
        if (p1->data <= p2->data) {
            // 将这个节点与head3连接上
            p3->next = p1;
            // p3指向p1, 为下一次连接做准备
            p3 = p1;
            p1 = p1->next;
        } else {
            // 将这个节点与head3连接上
            p3->next = p2;
            // p3指向p1, 为下一次连接做准备
            p3 = p2;
            p2 = p2->next;
        }
    }
    // 将非空表的剩余部分与head3相连
    p3->next = p1 ? p1 : p2;
    free(head2);
}

void PrintNodeList(Linklist &head) {
    Linklist p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
}

int main() {
    Linklist head1, head2, head3;
    head1 = InitHeadNode(head1);
    head2 = InitHeadNode(head2);
    head3 = InitHeadNode(head3);

    int n;
    scanf("%d", &n);
    head1 = CreateNodeList(head1, n);
    scanf("%d", &n);
    head2 = CreateNodeList(head2, n);

    MergeNode(head1, head2, head3);

    PrintNodeList(head3);
}