两个有序链表序列的合并（c语言实现）

た入场券 2021-11-17 11:26 282阅读 0赞

### 题目 ###

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

#### 函数接口定义： ####

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

### 代码 ###

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;
    }

### 结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211116/39b5e2b1cd6e46edbdc84697e40c2b82.png