两个单链表元素交叉合并

Question

pta显示段错误，不知道哪里错了

题目：

设带头结点的线性单链表A={a1,a2,...,am}，B={b1,b2,...,bn} 。试编写算法按下列规则合并A、B为线性单链表C，使得

 C={a1,b1,a2,b2,...am,bm,...,bn} ，  m<=n
 或者
 C={b1,a1,b2,a2,...,bn,an,...,am} ,   m>n

其中 La 和 Lb 都是用户传入的参数，分别为待合并单链表的头指针。函数须返回合并后的单链表的头指针。

函数接口定义：

LinkList CombineList(LinkList La,LinkList Lb);

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct node
{
DataType data;
struct node *next;
}LNode,*LinkList;

LinkList CreatLinkList(); //创建带头结点单链表,并返回头指针。
void PrintLinkList(LinkList H);//依次输出单链表H中各个元素结点，若为空表则输出NONE。
LinkList CombineList(LinkList La,LinkList Lb);
main()
{
LinkList la,lb;
la = CreatLinkList();
lb = CreatLinkList();
la=CombineList(la,lb);
PrintLinkList(la);
}

LinkList CreatLinkList()
{
int n,i;
LNode *nw,*rear=NULL,head=NULL;
head=(LNode)malloc(sizeof(LNode));
rear=head;
scanf("%d",&n);//接收结点总数
for(i=0;i<n;i++)
{
nw=(LNode*)malloc(sizeof(LNode));
scanf("%d",&nw->data);
rear->next=nw;
rear=nw;
}
rear->next=NULL;
return head;
}

void PrintLinkList(LinkList H)
{
LNode *p;
if(!(H->next))
{
printf("NONE\n");
return;
}
for(p=H->next;p;p=p->next)
printf("%d ",p->data);
printf("\n");
}

/* 请在这里填写答案 */

我的答案：

LinkList CombineList(LinkList La,LinkList Lb)
{
    int m=0,n=0;
    LinkList p=La;
    LinkList q=Lb;
    LinkList p1=La;
    LinkList p2=p1->next;
    LinkList q1=Lb;
    LinkList q2=q1->next;
    LinkList h;
    while(p)
    {
        p=p->next;
        m++;
    }
    while(q)
    {
        q=q->next;
        n++;
    }
    if(m<=n)
    {
        h=La;
        while(p1&&q1)
        {
            q1->next=p1->next;
            p1->next=q1;
            q1=q2;
            p1=p2;
            p2=p2->next;
            q2=q2->next;
            m--;
            n--;
        }
        if(p1)
        {
            q1->next=p1;
        }
        if(p2)
        {
            p1->next=q1;
        }
        free(Lb);
    }
    else
    {
        h=Lb;
        while(p1&&q1)
        {
            p1->next=q1->next;
            q1->next=p1;
            q1=q2;
            p1=p2;
            p2=p2->next;
            q2=q2->next;
            m--;
            n--;
        }
        if(q1)
        {
            p1->next=q1;
        }
        if(p1)
        {
            q1->next=p1;
        }
        free(La);
    }
   return h;
}

Answer 1

供参考：

#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct node
{
    DataType data;
    struct node* next;
}LNode, * LinkList;
LinkList CreatLinkList(); //创建带头结点单链表,并返回头指针。
void PrintLinkList(LinkList H);//依次输出单链表H中各个元素结点，若为空表则输出NONE。
LinkList CombineList(LinkList La, LinkList Lb);
int main()
{
    LinkList la, lb;
    la = CreatLinkList();
    lb = CreatLinkList();
    la = CombineList(la, lb);
    PrintLinkList(la);
    return 0;
}

LinkList CreatLinkList()
{
    int n, i;
    LNode* nw, * rear = NULL, *head = NULL;
    head = (LNode*)malloc(sizeof(LNode));
    rear = head;
    scanf("%d", &n);//接收结点总数
    for (i = 0; i < n; i++)
    {
        nw = (LNode*)malloc(sizeof(LNode));
        scanf("%d", &nw->data);
        rear->next = nw;
        rear = nw;
    }
    rear->next = NULL;
    return head;
}

void PrintLinkList(LinkList H)
{
    LNode* p;
    if (!(H->next))
    {
        printf("NONE\n");
        return;
    }
    for (p = H->next; p; p = p->next)
        printf("%d ", p->data);
    printf("\n");
}

/* 请在这里填写答案 */

LinkList CombineList(LinkList La, LinkList Lb)
{
    int m = 0, n = 0, i = 0;
    LinkList p = La->next;
    LinkList q = Lb->next;
    LinkList p1 = La->next;
                  //LinkList p2 = p1->next;
    LinkList q1 = Lb->next;
                  //LinkList q2 = q1->next;
    LinkList h, head;
    while (p) { p = p->next; m++; }
    while (q) { q = q->next; n++; }
    if (m <= n)
    {
        head = h = La;
        while (p1 && q1)
        {
            i++;
            if (i % 2) {
                head->next = p1;
                head = p1;
                p1 = p1->next;
            }
            else {
                head->next = q1;
                head = q1;
                q1 = q1->next;
            }
#if 0
            q1->next = p1->next;
            p1->next = q1;
            q1 = q2;
            p1 = p2;
            p2 = p2->next;
            q2 = q2->next;
            m--;
            n--;
#endif
        }
        if (p1)
        {
            head->next = p1;//q1->next = p1;
        }
        if (q1)
        {
            head->next = q1;//p1->next = q1;
        }
        free(Lb);
    }
    else
    {
        head = h = Lb;    //修改
        while (p1 && q1)
        {
            i++;
            if (i % 2) {
                head->next = q1;
                head = q1;
                q1 = q1->next;
            }
            else {
                head->next = p1;
                head = p1;
                p1 = p1->next;
            }
        }
#if 0
            p1->next = q1->next;
            q1->next = p1;
            q1 = q2;
            p1 = p2;
            p2 = p2->next;
            q2 = q2->next;
            m--;
            n--;
    }
#endif
        if (q1)
        {
            head->next = q1;  //p1->next = q1;
        }
        if (p1)
        {
            head->next = p1; //q1->next = p1;
        }
        free(La);
    }
    return h;
}