任务描述
本关任务：给定两个非递减的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个非递增的有序序列C，序列C允许有重复的数据。要求空间复杂度为O(1)。

编程要求
输入
多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。

输出
对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

测试说明
平台会对你编写的代码进行测试：

测试输入：
5 5
1 3 5 7 9
2 4 6 8 10
5 6
1 2 2 3 5
2 4 6 8 10 12
0 0

预期输出：
10 9 8 7 6 5 4 3 2 1
12 10 8 6 5 4 3 2 2 2 1`

答案

#include <iostream>
using namespace std;
#define MAX 100
typedef struct LNode
{
    
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{
    //后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
    
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
void PrintList(LinkList &L)
{
    //打印依次输出链表中的数据
    L=L->next;
    while(L){
    
        if(L->next!=NULL) cout<<L->data<<" ";
        else cout<<L->data;
        L=L->next;
    }
    cout<<endl;
}
void MergeList(LinkList &LA,LinkList &LB,LinkList &LC)
{
    //求基于链表的两个非递减有序序列的合并
    /**************begin************/
    
    // 先让LC指空
    LC = NULL;
    // 两个原链表指针分别指向两个链表(LA,LB)中正在被比较的节点
    LA = LA -> next, LB = LB -> next;
    // 把较小的那个节点指向LC,即往前指，然后小的那个的当前指针/正在被比较的节点往后走
    while (LA && LB)
    {
    
        if (LA -> data < LB -> data) {
    
            LNode * tmp = LA -> next;
            LA -> next = LC;
            LC = LA;
            LA = tmp;
        }
        else {
    
            LNode * tmp = LB -> next;
            LB -> next = LC;
            LC = LB;
            LB = tmp;
        }
    }
    while (LA) {
    
            LNode * tmp = LA->next;
            LA->next = LC;
            LC = LA;
            LA = tmp;
        }
    while (LB) {
    
        LNode * tmp = LB->next;
        LB->next = LC;
        LC = LB;
        LB = tmp;
    }
    LNode * tmp = LC;
    LC = new LNode;
    LC -> next = tmp;

    /**************end************/
}
int main()
{
    
    int n,m;
    while(cin>>n>>m)
    {
    
        if(n==0&&m==0) break;
        LinkList LA,LB,LC;
        CreateList_R(LA,n);
        CreateList_R(LB,m);
        MergeList(LA,LB,LC);
        PrintList(LC);
    }
    return 0;
}

笔者的代码其实和题目要求有个小误差：我在MergeList()函数里为LC申请了空间，这就和题目要求的O(1)空间复杂度不符，但实际开发中可以忽略，如果想完全达到题目要求的O(1)复杂度也可以，那在MergeList()函数中就这么写：

/* 为了避免动态分配内存，将MergeList函数中创建新节点的操作改为复用已有节点，而不是动态分配新的节点。这样可以保持空间复杂度为O(1)。*/
void MergeList(LinkList &LA, LinkList &LB, LinkList &LC) {
    
    LC = NULL;
    LA = LA->next; 
    LB = LB->next;
    while (LA && LB) {
    
        if (LA->data < LB->data) {
    
            LNode *tmp = LA->next;
            LA->next = LC;
            LC = LA;
            LA = tmp;
        } else {
    
            LNode *tmp = LB->next;
            LB->next = LC;
            LC = LB;
            LB = tmp;
        }
    }
    while (LA) {
    
        LNode *tmp = LA->next;
        LA->next = LC;
        LC = LA;
        LA = tmp;
    }
    while (LB) {
    
        LNode *tmp = LB->next;
        LB->next = LC;
        LC = LB;
        LB = tmp;
    }
}