将两个有序单链表合并成一个有序单链表的递归做法（C语言）

野性酷女 2022-03-26 05:26 180阅读 0赞

**一、递归算法如下：**

/*有序单链表的合并，生成一个有序的单链表，递归做法*/
    Linklist MergerLinklist(Linklist L0,Linklist L1)
    {
    	LNode *Newhead;
    	if(L0 == NULL)
    	{
    		return L1;
    	}
    	else if(L1 == NULL)
    	{
    		return L0;
    	}
    	else
    	{
    		if(L0->data < L1->data )
    		{
    			Newhead=L0;
    			Newhead->next = MergerLinklist(L0->next,L1);
    		}
    		else
    		{
    			Newhead=L1;
    			Newhead->next = MergerLinklist(L1->next,L0);
    		}	
    	}
    	return Newhead;	
    }

**二、实例程序代码如下：**

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define  LEN  5
    
    typedef  int  Elemtype;
    typedef struct LNode{
    	Elemtype data;
    	struct LNode *next;
    }LNode,*Linklist;
    
    /*单链表初始化*/
    void Init_Linklist(Linklist *L)
    {
    	*L=(Linklist)malloc(sizeof(LNode));
    	assert(*L != NULL);
    	(*L)->next=NULL;	
    }
    
    /*创建单链表*/ 
    void Create_Linklist(Linklist *L)
    {
    	LNode *p,*q;
    	p = *L;
    	for(int i=0;i<LEN;i++)
    	{
    		q=(Linklist)malloc(sizeof(LNode));
    		assert( q != NULL);
    		scanf("%d",&q->data);
    		p->next=q;
    		p=q;
    	}
    	p->next=NULL;
    }
    
    /*有序单链表的合并，生成一个有序的单链表，递归做法*/
    Linklist MergerLinklist(Linklist L0,Linklist L1)
    {
    	LNode *Newhead;
    	if(L0 == NULL)
    	{
    		return L1;
    	}
    	else if(L1 == NULL)
    	{
    		return L0;
    	}
    	else
    	{
    		if(L0->data < L1->data )
    		{
    			Newhead=L0;
    			Newhead->next = MergerLinklist(L0->next,L1);
    		}
    		else
    		{
    			Newhead=L1;
    			Newhead->next = MergerLinklist(L1->next,L0);
    		}	
    	}
    	return Newhead;	
    }
    
    /*单链表的输出*/ 
    void Print_Linklist(Linklist *L)
    {
    	LNode *p;
    	p = *L;
    	while(p)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Linklist L0,L1,head=NULL;
    	
    	/*单链表L0的初始化*/ 
    	printf("请输入第一个有序单链表：\n");
    	Init_Linklist(&L0);
    	Create_Linklist(&L0);
    	
    	/*单链表L1的初始化*/
    	printf("请输入第一个有序单链表：\n");
    	Init_Linklist(&L1);
    	Create_Linklist(&L1);
    	
    	/*单链表的有序合并*/
    	head=MergerLinklist(L0->next,L1->next);
    	printf("单链表合并后为：\n");
    	Print_Linklist(&head);
    	return 0;
    }

**二、运行截图为：**  
![在这里插入图片描述][20190115195209120.png]

[20190115195209120.png]: /images/20220326/67d54fa2785f4f01b3440d04b0c78e98.png