YaYa很开心 2022-09-21 23:22 采纳率: 81.3%
浏览 80
已结题

两个单链表元素交叉合并

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;
}

  • 写回答

1条回答 默认 最新

  • qzjhjxj 2022-09-22 14:56
    关注

    供参考:

    #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;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 10月7日
  • 已采纳回答 9月29日
  • 创建了问题 9月21日

悬赏问题

  • ¥20 keepalive配置业务服务双机单活的方法。业务服务一定是要双机单活的方式
  • ¥50 关于多次提交POST数据后,无法获取到POST数据参数的问题
  • ¥15 win10,这种情况怎么办
  • ¥15 如何在配置使用Prettier的VSCode中通过Better Align插件来对齐等式?(相关搜索:格式化)
  • ¥100 在连接内网VPN时,如何同时保持互联网连接
  • ¥15 MATLAB中使用parfor,矩阵Removal的有效索引在parfor循环中受限制
  • ¥20 Win 10 LTSC 1809版本如何无损提升到20H1版本
  • ¥50 win10 LTSC 虚拟键盘不弹出
  • ¥30 微信小程序请求失败,网页能正常带锁访问
  • ¥15 Matlab求解微分方程,如何用fish2d进行预优?