思路

链表合并很简单，合并完还是一个非递减数列，我们只用开三个相邻A(最前面)BC(最后面)结点指针（B=A->next;C=A->next->next;），若B=C，则A->next=C;

#include<iostream>
#include<string.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;                 //声明类型int类型为Status
typedef Book ElementType;
#define MAXSIZE 10000               //图书表可能达到的最大长度 
typedef struct tagBook
{
    int i;
}Book;
typedef struct LNode
{
    ElementType data;
    struct LNode *next;
}LNode,*LinkList;
Status init(LinkList &L)
{
    L=new LNode;
    L->next=NULL;
    return OK;
}
Status Length_L(LinkList &L)
{
    LinkList p=L->next;
    int count=0;
    while(p)
    {
        count++;
        p=p->next;
    }
    return count;
}
int main()
{
    int n,m;
    LinkList A,B,C,a,b,c,p,q,r;
    while(cin>>n>>m&&(n||m))     //输入no、name、price
    {
        init(A);
        init(B);
        a=A;
        b=B;
        for(int i=0;i<n;i++)
        {
            LinkList p=new LNode;
            p->next=NULL;
            cin>>p->data.i;
            A->next=p;
            A=p;
        }
        for(int i=0;i<m;i++)
        {
            LinkList p=new LNode;
            p->next=NULL;
            cin>>p->data.i;
            B->next=p;
            B=p;
        }
        LinkList C,c;
        init(C);
        c=C;
        A=a->next;B=b->next;
        while(A&&B)
        {
                int val1,val2;
                val1=A->data.i;
                val2=B->data.i;
                if(val1<val2)
                {
                    c->next=A;
                    c=A;
                    A=A->next;
                }else
                {
                    c->next=B;
                    c=B;
                    B=B->next;
                }
        }
        if(!A)
        {
            delete a;
            c->next=B;
        }else if(!B)
        {
            delete b;
            c->next=A;
        }   
        
        p=C;q=p->next;r=q->next;
        while(1)
        {
            int n=Length_L(C);
            if(n>1)
            {
                if(!r)
                    break;
                if(q->data.i==r->data.i)
                {
                    p->next=r;
                    q=r;r=r->next;
                }else
                {
                    p=p->next;q=p->next;r=q->next;
                }

            }else
                break;
        }
        c=C->next;
        while(c->next)
        {
            cout<<c->data.i<<" ";
            c=c->next;
        }
        cout<<c->data.i<<endl;
    }
    return 0;                       //0：表示无错误退出。1：表示异常退出。

}

基于链表的两个递增有序序列的合并
发布时间: 2017年9月18日 00:54 最后更新: 2017年9月18日 12:00 时间限制: 1000ms 内存限制: 128M

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

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

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

样例输入1
5 5
1 3 5 7 9
2 4 6 8 10
3 4
1 5 9
1 2 5 9
0 0
样例输出1
1 2 3 4 5 6 7 8 9 10
1 2 5 9