链表合并--给定两个元素有序（从小到大）的链表，要求将两个链表合并成一个有序（从小到大）链表，

输入描述:

第一行输入第一个链表的结点数S1，S1<=100。
第二行输入S1个整数，两两之间用空格隔开。
第三行输入第二个链表的结点数S2，S2<=100。
第四行输入S2个整数，两两之间用空格隔开。

输出描述:

输出合并之后的链表结果，两两之间用空格隔开，末尾没有空格。

#include <stdio.h>
#include <stdlib.h>
 
//先生成两个链表，然后依次遍历两个链表，并用数组保存两个链表的元素值，对数组进行快速排序，排序后的元素生成一个新链表即可。
 
typedef struct node
{
	int data;
	struct node * next;
}Node;
Node* init(); //链表初始化，生成头结点
void create(Node *L,int n); //尾插法生成长度为n的链表
void quicksort(int s[],int low,int high); //快速排序
int partition(int s[],int low,int high);
 
int main(){
	int n1,n2;
	Node *L1=init();
	scanf("%d",&n1);
	create(L1,n1);
	Node *L2=init();
	scanf("%d",&n2);
	create(L2,n2);
	int s[200]={0};
	int n=n1+n2;
	Node *tmp=L1->next;
	for(int i=0;i<n1;i++)
	{
		s[i]=tmp->data;
		tmp=tmp->next;
	}
	tmp=L2->next;
	for(int i=n1;i<n;i++)
	{
		s[i]=tmp->data;
		tmp=tmp->next;
	}
	quicksort(s,0,n-1);
	Node *L=init();
	Node *p=L;
	for(int i=0;i<n;i++)
	{
		Node *q=(Node*)malloc(sizeof(node));
		q->data=s[i];
		q->next=NULL;
		p->next=q;
		p=q;
	}
	p=L;
	for(int i=0;i<n;i++)
	{
		p=p->next;
		printf("%d ",p->data);
	}
}
 
Node* init(){ //链表初始化，生成头结点
	Node *L=(Node*)malloc(sizeof(node));
	L->next=NULL;
	return L;
}
 
void create(Node *L,int n){  //尾插法生成长度为n的链表
	Node *p=L;
	for(int i=0;i<n;i++)
	{
		Node *q=(Node*)malloc(sizeof(node));
		int e;
		scanf("%d",&e);
		q->data=e;
		q->next=NULL;
		p->next=q;
		p=q;
	}
}
 
void quicksort(int s[],int low,int high){  //快速排序
	if(low<high){
		int pivotpos=partition(s,low,high);
		quicksort(s,low,pivotpos-1);
		quicksort(s,pivotpos+1,high);
	}
 
}
 
int partition(int s[],int low,int high)
{
	int pivot=s[low];
	while(low<high)
	{
		while(low<high&&pivot<=s[high])
			high--;
		s[low]=s[high];
		while(low<high&&pivot>=s[low])
			low++;
		s[high]=s[low];
	}
	s[low]=pivot;
	return low;
}

运行结果：