PTA 两个有序链表序列的合并
2024-10-19 06:05:33
6-5 两个有序链表序列的合并 (15 分)
本题要求实现一个函数,将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义:
List Merge( List L1, List L2 );
其中List
结构定义如下:
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存储结点数据 */
PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
L1
和L2
是给定的带头结点的单链表,其结点存储的数据是递增有序的;函数Merge
要将L1
和L2
合并为一个非递减的整数序列。应直接使用原序列中的结点,返回归并后的带头结点的链表头指针。
裁判测试程序样例:
#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;
}
/* 你的代码将被嵌在这里 */
输入样例:
3
1 3 5
5
2 4 6 8 10
输出样例:
1 2 3 4 5 6 8 10
NULL
NULL
作者: DS课程组
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
1 List Merge( List L1, List L2 ){
2 List L=(List)malloc(sizeof(struct Node));
3 List p=L;
4 List pa=L1->Next;
5 List pb=L2->Next;
6 while(pa&&pb){
7 if(pa->Data<=pb->Data){
8 p->Next=pa;
9 p=pa;
10 pa=pa->Next;
11 }
12 else{
13 p->Next=pb;
14 p=pb;
15 pb=pb->Next;
16 }
17 }
18 p->Next=pa?pa:pb;
19 L1->Next=NULL;
20 L2->Next=NULL;
21 return L;
22 }
最新文章
- [软件测试基础3]基于Jemter的压力测试
- android应用中增加权限判断
- 标清与高清,720p和1080p,720i和720p,h264与h265
- 获取某个Group中所有对象的DisplayName
- Mybatis 实用
- mongodb在ubuntu下的couldn‘t remove fs lock errno:9 Bad file descriptor的错误
- Jvm基础(1)-Java运行时数据区
- qDebug 学习小结
- 一个简单二叉树的C++实现(一)
- 安卓Visibility属性
- Input file 文本框美化
- iOS开发之Xcode常用调试(Debug)技巧总结
- SpringBoot多模块项目打包问题
- [20181130]control file sequential read.txt
- 漏洞复现——httpd换行解析漏洞
- 用Python下载美国国家气候数据中心(NCDC)的气候数据
- JavaScript-switch-case运用-案例
- 关于 qtchooser
- CodeForces - 586C Gennady the Dentist 模拟(数学建模的感觉)
- poj3080kmp或者暴力