数据结构题，学校oj平台上的，一样的输入内容，出现的结果每次都不一样

Question

数据结构题，学校oj平台上的，一样的输入内容，出现的结果每次都不一样

问题描述：

基于链表的两个递增有序序列的合并
描述
给定两个递增的整数序列A和B，利用链表表示序列A和B，将A和B合并为一个递增的有序序列C，序列C不允许有重复的数据。要求空间复杂度为O(1)。
输入
多组数据，每组数据有三行，第一行为序列A和B的长度n和m，第二行为序列A的n个元素，第三行为序列B的m个元素（元素之间用空格分隔）。n=0且m=0时输入结束。
输出
对于每组数据输出一行，为合并后的序列，每个数据之间用空格分隔。

题目地址：http://www.bjfuacm.com/problem/225

代码：

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

#define OK 1;
#define OVERFLOW -1;

typedef int Status;

typedef struct LNode{
    int data;
    struct LNode *next;
    int length;
}LNode,*LinkList;

Status InitList(LinkList &L)
{
    L=(LNode*)malloc(sizeof(LinkList));
    if(L==NULL)
        return OVERFLOW;
    L->next=NULL;
    L->length=0;
    return OK;
}

Status CreatList(LinkList &L)
{
    LinkList p=L;
    for(int i=0;i<=L->length-1;i++)
    {
        LinkList q;
        q=(LNode*)malloc(sizeof(LinkList));
        scanf("%d",&q->data);
        q->next=NULL;
        p->next=q;
        p=q;
    }
    return OK;
}

Status MergeList(LinkList &A,LinkList &B,LinkList &C)
{
    LinkList p=A;
    LinkList q=B;
    LinkList r=C;
    while(p->next!=NULL&&q->next!=NULL)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        if(p->next->data==q->next->data)
        {
            s->data=p->next->data;
            p=p->next;
            q=q->next;
        }
        else
        {
            if(p->next->data<q->next->data)
            {
                s->data=p->next->data;
                p=p->next;
            }
            else
            {
                s->data=q->next->data;
                q=q->next;
            }
        }
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
    }
    while(p->next)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        s->data=p->next->data;
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
        p=p->next;
    }
    while(q->next)
    {
        LinkList s;
        s=(LNode*)malloc(sizeof(LinkList));
        s->data=q->next->data;
        s->next=NULL;
        r->next=s;
        r=s;
        C->length++;
        q=q->next;
    }
    return OK;
}

Status OutputList(LinkList &L)
{
    LinkList p=L;
    while(p->next)
    {
        printf("%d ",p->next->data);
        p=p->next;
    }
    return OK;
}

int main()
{
    for(int i=0;;i++)
    {
        LinkList A,B;
        InitList(A);
        InitList(B);
        scanf("%d%d",&A->length,&B->length);
        if(A->length==0&&B->length==0)
            break;
        else
        {
            LinkList C;
            InitList(C);
            CreatList(A);
            CreatList(B);
            MergeList(A,B,C);
            OutputList(C);
            free(A);
            free(B);
            free(C);
            printf("\n");
        }

    }
    return 0;
}

输入：

5 5
1 3 5 7 9
2 4 6 8 10
3 4
1 5 9
1 2 5 9
0 0

正确输出：

1 2 3 4 5 6 7 8 9 10
1 2 5 9

运行结果

第一次：
1 2 3 4 5 6 7 8 9 10
第二次：
1 2 3 4 5
第三次：
1 2 3 4 5 6
……

一样的输入样例，每次出现的结果都不一样。
望各位帮一下！

Answer 1

#include <iostream>

using namespace std;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void InitList(LinkList &L)  //初始化
{
    L = new LNode;
    L->next = NULL;
}

void CreatList(LinkList &L,int n)  //尾插法建表
{
    LinkList rear = L;
    for(int i=0;i<n;i++)
    {
        int temp;
        cin>>temp;
        LinkList h = new LNode;
        h->data = temp;
        rear->next = h;
        rear = h;
    }
    rear->next = NULL;
}

void print_list(LinkList &L)   //遍历输出表中元素
{
    LinkList p = L->next;
    while(p!=NULL)
    {
        cout<<p->data;
        if(p->next!=NULL)
        {
            cout<<' ';
        }
        p = p->next;
    }
    cout<<endl;
}

void Merge_list(LinkList &A,LinkList &B)   //合并两个表并输出
{
    LinkList C = new LNode;
    C->next = NULL;
    LinkList pa = A->next;
    LinkList pb = B->next;
    LinkList pc = C;
    while(pa!=NULL&&pb!=NULL)
    {
        if(pa->data>pb->data)
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
        else if(pa->data<pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            pb = pb->next;
        }
    }
    if(pa!=NULL&&pb==NULL)
    {
        pc->next = pa;
    }
    if(pb!=NULL&&pa==NULL)
    {
        pc->next = pb;
    }
    print_list(C);
}

int main()
{
    while(true)
    {
        int n,m;
        cin>>n>>m;
        if(n==0&&m==0)
        {
            break;
        }
        LinkList A,B;
        InitList(A);
        InitList(B);
        CreatList(A,n);
        CreatList(B,m);
        Merge_list(A,B);
    }
}