02-线性结构1 两个有序链表序列的合并（15 point(s)）
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。 函数接口定义：
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
思路 因为 本来两个链表 就是有序的 所以 如果两个链表当前所指的地址 都不是 NULL地址的话 就比较两个值的大小 取值小的地址 当做 目标链表的下一个地址 如果 有一个链表 目前所指的地址 是NULL 地址的话 就直接 指向另一个地址就可以了
AC代码
#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; } /* 你的代码将被嵌在这里 */ List Read() { int n; scanf("%d", &n); List L = (List) malloc (sizeof(PtrToNode)); L -> Next = NULL; if (n) { List r = L; for (int i = 0; i < n; i++) { List p = (List) malloc (sizeof(struct Node)); scanf("%d", &(p -> Data)); r -> Next = p; r = p; } r -> Next = NULL; } return L; } void Print(List L) { L = L -> Next; if (L == NULL) printf("NULL\n"); else { for (int i = 0; ; i++) { if (i) printf(" "); printf("%d", L -> Data); L = L -> Next; if (L == NULL) break; } printf("\n"); } } List Merge( List L1, List L2 ) //仅提交此部分就可以 { List ans = (List) malloc (sizeof(PtrToNode)); List p1, p2; p1 = L1 -> Next; p2 = L2 -> Next; List r = ans; List temp; while (p1 && p2) { if (p1 && p2) { if (p1 -> Data < p2 -> Data) { temp = p1; p1 = p1 -> Next; } else { temp = p2; p2 = p2 -> Next; } } r -> Next = temp; r = temp; } if (p1) r -> Next = p1; else r -> Next = p2; L1 -> Next = NULL; L2 -> Next = NULL; return ans; }转载于:https://www.cnblogs.com/Dup4/p/9433174.html
相关资源：将两个链表的合并实验报告