不破坏原表合并单链表

//设计算法合并两个单链表
#include<iostream>
#include<stdlib.h>

typedef struct slist
{
	int data;
	struct slist *next;
}list;
using namespace std;

void printlist(list *l);//打印单链表
void mergelist(list *l1,list *l2,list *&l3);//合并单链表
list* creatlist(list *l);//创建单链表 

int main(void)
{
	list l1;
	list l2;
	list *p,*q;
	p = creatlist(&l1);
	q = creatlist(&l2);
	list *r;
	mergelist(p,q,r);
	printlist(r);
	return 0;
}

void mergelist(list *l1,list *l2,list *&l3)
{
	list *p = l1->next ,*q = l2->next ;
	list *r;
	l3 = (list *)malloc(sizeof(list));
	r = l3;
	free(l2);//释放l2头结点 
	while(p != NULL && q != NULL)
	{
		//破坏原表 
		/*r->next = p;
		r = p;
		p = p->next ;
		r->next = q;
		r = q;
		q = q->next ;*/
		
		//新建表
		list *s = (list *)malloc(sizeof(list));
		s->data = p->data ;
		r->next = s;
		r = s;
		p = p->next ;
		s = (list *)malloc(sizeof(list));
		s->data = q->data ;
		r->next = s;
		r = s;
		q = q->next ; 
	}
	/*if(q == NULL)
	{
		p = q;
	}
	r->next = p;*/
	while(p != NULL)
	{
		list *s = (list *)malloc(sizeof(list));
		s->data = p->data ;
		r->next = s;
		r = s;
		p = p->next ;
	}
	while(q != NULL)
	{
		list *s = (list *)malloc(sizeof(list));
		s->data = q->data ;
		r->next = s;
		r = s;
		q = q->next ;
	}
	r->next = NULL;
}

list* creatlist(list *l)
{
	l = (list *)malloc(sizeof(list));
	l->next = NULL;
	list *r,*s;
	r = l;
	int x;
	cin>>x;
	while(x != 0)
	{
		s = (list *)malloc(sizeof(list));
		s->data = x;
		r->next = s;
		r = s;
		cin>>x;
	}
	r->next = NULL; 
	return l;
}

void printlist(list *l)
{
	if(l->next == NULL)
	{
		printf("该链表无元素:");
	}
	else
	{
		list *p = l->next ;
		while(p != NULL)
		{
			printf("%d ",p->data );
			p= p->next ;
		}
	}
	printf("\n");
}