2018.3.15
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。 L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的； 函数Merge要将L1和L2合并为一个非递减的整数序列。 应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
// Add_two_List.cpp: 定义控制台应用程序的入口点。 //本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。 //L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的； //函数Merge要将L1和L2合并为一个非递减的整数序列。 //应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。 #include "stdafx.h" #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) ///当n不是0时 { List r = L; ///r是一个中间变量的节点 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) { List p = L->Next; if (p) { List r; r = L; while (r->Next) { r = r->Next; printf("%d ", r->Data); } } else { printf("NULL"); } printf("\n"); } List Merge(List L1, List L2) { List pa, pb, pc, L; L = (List)malloc(sizeof(struct Node)); pa = L1->Next;//过头结点 pb = L2->Next; pc = L; while (pa && pb) { if (pa->Data <= pb->Data) { pc->Next = pa; pc = pa; pa = pa->Next; } else { pc->Next = pb; pc = pb; pb = pb->Next; } } pc->Next = pa ? pa : pb;//pa有值则链pa，否则链pb L1->Next = NULL; L2->Next = NULL; return L; }#Coding一小时，Copying一秒钟。留个言点个赞呗，谢谢你#
