Loading... 本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。 ### 函数接口定义: ```c++ hljs List Merge( List L1, List L2 ); ``` 其中`List`结构定义如下: ```c++ hljs typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ ``` `L1`和`L2`是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数`Merge`要将`L1`和`L2`合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。 ### 裁判测试程序样例: ```c++ hljs #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表;空链表将输出NULL */ List Merge( List L1, List L2 ); int main() { List L1, L2, L; L1 = Read(); L2 = Read(); L = Merge(L1, L2); Print(L); Print(L1); Print(L2); return 0; } /* 你的代码将被嵌在这里 */ ``` ### 输入样例: ```in 3 1 3 5 5 2 4 6 8 10 ``` ### 输出样例: ```out 1 2 3 4 5 6 8 10 NULL NULL ``` ### 答案: 最开始我连题目都读不懂,真的不知道他要我写几个函数。 实现步骤: 1. 获得head1和head2中数据值较小的节点,并设置为合并后链表的首节点。 2. 通过循环,一次获得链表1和链表2中数据值较小的节点,并添加到合并后链表的末尾。 3. 当步骤2执行完毕,如果某一个链表中的首节点不为NULL,则将链表首节点及其之后的节点添加到合并后链表的末尾。 ```c List Merge( List L1, List L2 ){ List L,p,q,r; L=(List)malloc(sizeof(struct Node)); //新建一个结点 p=L1->Next; //p指向L1最小值 q=L2->Next; //q指向L2最小值 L->Next=NULL; r=L; //r指向L while(p!=NULL&&q!=NULL) //p、q都不空,选取p、q所指结点较小者插入L的尾部 { if(p->Data<=q->Data){ r->Next=p; p=p->Next; r=r->Next; }else{ r->Next=q; q=q->Next; r=r->Next; } } if(p!=NULL) r->Next=p; if(q!=NULL) r->Next=q; L1->Next=NULL; L2->Next=NULL; return L; } ``` 最后修改:2021 年 06 月 04 日 © 禁止转载 打赏 赞赏作者 支付宝微信 赞 1 如果觉得我的文章对你有用,请随意赞赏