解题思路:链表合并不需要再创建空间,只需要进行穿针引线,把两个单链表中的结点，按非递减的顺序串联起来即可。
注意:单链表的头指针不可以移动

# include <iostream>
using namespace std;

typedef struct LNode {
    int data; //结点的数据域
    struct LNode* next; //结点的指针域
}LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

//尾插法创建单链表
void CreateList_R(LinkList& L, int n) {
    L = new LNode;
    L->next = NULL; //创建一个空的头结点
    LNode* r = L; //尾指针
    for (int i = 0; i < n; i++) {
        LNode* p = new LNode;
        cin >> p->data;
        r->next = p;
        r = p;
    }
    r->next = NULL;//将最后一个结点的指针域置空
}

//链表合并
LinkList MergeList(LinkList& L1, LinkList& L2) {
    LNode* L = L1;  //L是合并的新链表头指针,L指向L1的头结点
    LNode* r = L; //尾指针永远指向链表尾部
    LNode* p = L1->next, * q = L2->next;//p指针指向L1的第一个元素,q指针指向L2的第一个元素
    while (p && q) {
        if (p->data <= q->data) {//把p指向的结点串起来
            r->next = p;
            r = p;
            p = p->next;//p后移到下一结点
        }
        else {//把q指向的结点串起来
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    //退出循环的条件:1、p为空;  2、q为空
    if (!p) r->next = q;//p为空
    if (!q) r->next = p;//q为空
    //或者r->next = p ? p : q;
    delete L2;
    return L;
}

//打印链表
void ListPrint(LinkList L) {
    //顺序输出单链表
    LNode* p = L->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L1, L2, L; //L是合并后链表的头指针
    int S1, S2;
    cin >> S1;
    CreateList_R(L1, S1);
    cin >> S2;
    CreateList_R(L2, S2);
    L = MergeList(L1, L2);
    ListPrint(L);

    return 0;
}