#include <bits/stdc++.h>

using namespace std;

//定义单链表结点类型
typedef struct LNode
{
    int data;           //每个节点存放一个数据元素
    struct LNode *next; //指针指向下一个节点
} LNode, *LinkList;

//LNode强调返回的是一个结点
//LinkList强调这是一个单链表

//初始化一个单链表(带头结点)
bool InitList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
    if (L == NULL)
    { //内存不足，分配失败
        return false;
    }
    else
    {
        L->next = NULL; //头结点之后暂时还没有结点
        //养成好习惯，只要是初始化单链表，都先把头指针指向NULL
    }
    return true;
}

//尾插法正向建立单链表
LinkList ListTailInsert(LinkList &L)
{
    InitList(L);      //初始化空表
    LNode *r = L, *s; //r为表尾指针
    int x;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        //在r结点之后插入元素x
        r = s;
        //r指向新的表尾结点
        //永远保持r指向最后一个结点
        scanf("%d", &x);
    }
    r->next = NULL; //尾结点指针置空
    return L;
}

//打印函数（带头结点）
void print(LinkList &L)
{
    LNode *p = L->next;

    while (p != NULL)
    {
        if (p->next != NULL)
        {
            printf("%d->", p->data);
        }
        else
        {
            printf("%d", p->data);
        }
        p = p->next;
    }
    printf("\n");
}

//单链表归并操作
void merge(LinkList &A, LinkList &B, LinkList &C)
{
    LNode *p = A->next; //p跟踪A的最小值结点
    LNode *q = B->next; //q跟踪B的最小值结点
    LNode *r = C;       //r始终指向C的终端结点
    while (p != NULL && q != NULL)
    { //当p与q都不空时，取p与q所指结点中较小的插入C的尾部
        if (p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }
        else
        {
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    if (p != NULL)
    {
        r->next = p;
    }
    if (q != NULL)
    {
        r->next = q;
    }
}

int main()
{
    LinkList A, B, C;

    InitList(A);
    InitList(B);
    InitList(C);

    ListTailInsert(A);
    ListTailInsert(B);

    print(A);
    print(B);

    merge(A, B, C);

    print(C);

    return 0;
}

input:

1
3
5
9999
2
4
6
8
9999

output:

1->3->5
2->4->6->8
1->2->3->4->5->6->8