两个有序链表序列的合并-蒲公英云

两个有序链表序列的合并

PTA 01：两个有序链表序列的合并

一、题目

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义：

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;
    }
    /* 你的代码将被嵌在这里 */

输入样例：

输出样例：

1 2 3 4 5 6 8 10 
    NULL
    NULL

二、代码

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;
/* 你的代码将被嵌在这里 */
List Read(){
//    此函数的作用：创建链表并插入数据
    int n;
    scanf("%d",&n);
//    输入该链表中元素的个数
    List L=(List)malloc(sizeof(PtrToNode));
//    申请一个头节点
    L->Next=NULL;
//    先建立一个以L为头结点的空链表 
    if(n!=0){
        List r=L;
//    尾指针指向头结点 
    for(int i=0;i<n;i++){
        List p=(List)malloc(sizeof(struct Node));
        scanf("%d",&(p->Data));
        p->Next=NULL;
        r->Next=p;
        r=p;    
}  
r->Next=NULL;
    }
return L;
};
void Print(List L){
//    此函数的作用：打印链表中的元素 
    List P=L->Next;
 if(P!=NULL)
   {
       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 p1,p2,p,L;
    L = (List)malloc(sizeof(struct Node));
    p1=L1->Next;
    p2=L2->Next;
//  p1 p2指针分别指向两个表的第一个结点
    p=L;
//  p指向L的头结点
    while(p1!=NULL&&p2!=NULL){
        if(p1->Data<=p2->Data){
        p->Next=p1;
        p=p1;
        p1=p1->Next;
    }
    else{
        p->Next=p2;
        p=p2;
        p2=p2->Next;
    }
//  当L1 L2 均未到达表尾 依次摘取两表中值较小的结点插入到L最后
    }
     p->Next=p1?p1:p2;
     L1->Next=NULL;
     L2->Next=NULL;
     return L;
}; 
int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}