JSMS27-合并两个排序的链表-剑指offer17

题目描述，两个单链表按照增序排列，合并之后仍然为增序。

分析：这道题目相对来说比较简单，创建一个h指针，指向a的头结点，当a->data大于b->data时，h->next指向b，反之h->next指向a。最后结束的时候，如果a或者b其中一个不为空，则让h->next指向a或者b即可

#include <stdio.h>
#include <stdlib.h>

typedef struct d{
	int data;
	struct d *next;
}node;


node *Creat(int *a,int len)
{
	node *head=(node *)malloc(sizeof(node));
	head->data=NULL;
	node *ret=head;
	for(int i=0;i<len;i++)
	{
		node *s=(node *)malloc(sizeof(node));
		s->data=a[i];
		s->next=NULL;
		head->next=s;
		head=s;	
	}		
	return ret;
} 

node *merge(node *a,node *b)
{
	node *ret=a;	//以a链表头结点作为返回节点 
	node *q,*h;
	h=ret;
	a=a->next;
	q=b;
	b=b->next;
	free(q);		//删除b头结点 
	for(;a!=NULL&&b!=NULL;) //链表a或者b中的一个为空的时候弹出
	{
		if(a->data>b->data)       //当a->data大于b->data时候,//h->next指向b,反之指向a
		{
			h->next=b;        
			b=b->next;
			h=h->next;
		}else
		{
			h->next=a;
			a=a->next;
			h=h->next;	
		}
	}
	h->next=NULL;
	if(a!=NULL)
	{
		h->next=a;
	}
	if(b!=NULL)
	{
		h->next=b;
	}
	return ret;
} 

void Print(node *h)
{
	for(h=h->next;h;h=h->next)
	{
		printf("%d->",h->data);
	}
} 


int main()
{
	int a[]={1,3,5,7,9};
	int b[]={2,4,6,8,10,12,14,16};
	int len1=sizeof(a)/sizeof(a[0]);
	int len2=sizeof(b)/sizeof(b[0]);
	node *nodea=Creat(a,len1);
	node *nodeb=Creat(b,len2);
	node *ret=merge(nodea,nodeb);
	Print(ret);
}

复制代码