cpp1.cpp

2008软件公司笔试题：两个链表插入排序

#include  "iostream"
#include  "stdio.h"
#include "string.h"
#include "conio.h"
using namespace std;
typedef struct str
{
	int data;
	struct str *next;
}node;
int length(node *head)
{
	int n=0;
	node *p;
	p=head;
	while(p!=NULL)
	{
		p=p->next;
		n++;
	}
	return (n);
}
node *creat()
{
	node *head,*p,*s;
	int x,c=1;
	head=(node *)malloc(sizeof(node));
	p=head;
	while(c)
	{
		
		cout<<"\n intput the data:";
		cin>>x;
		if(x!=0)
		{
			s=(node *)malloc(sizeof(node));
		    s->data=x;
		
		    cout<<"  "<<s->data;
	  	    p->next=s;
		    p=s;
		}
	    else c=0;
	}
	head =head->next;
	p->next=NULL;

  //  cout<<"\n  "<<head->data;
    return(head);

}//print
void print(node *head)
{
	node *p ;
	int n;
	n=length(head);
	cout<<" \nrecords are "<<n<<"\n";
	p=head;
	if(head!=NULL)
		while(p->next!=NULL)
		{
			cout<<p->data<<"->";
			p=p->next;
		}
		cout<<p->data;
}
node *paixue(node *p,node *q)
{
	node *head,*p0,*p1;
	head=(node *)malloc(sizeof(node));
	p1=head;
	

	while(p!=NULL && q!=NULL)
	{
		p0=(node *)malloc(sizeof(node));
		if(p->data < q->data )
		{
			p0->data=p->data;
			p=p->next;
		}
		else
		{
			p0->data=q->data;
			q=q->next;
		}
		p1->next=p0;
		p1=p0;
		
	}
	
	if(q!=NULL)
	{
		
		while(q!=NULL)
		{
			p0=(node *)malloc(sizeof(node));
			p0->data=q->data;
			
			q=q->next;
			p1->next=p0;
	    	p1=p0;
			
		}
	}
	else
	{
		while(p!=NULL)
		{
			p0=(node *)malloc(sizeof(node));
			p0->data=p->data;
			p=p->next;
			p1->next=p0;
	    	p1=p0;
		}
	}
	head =head->next;
	p1->next=NULL;



	return(head);
}

void main()
{
	node *p,*q,*p1;
	p=creat();
	print(p);
	q=creat();
	print(q);
	p1=paixue(p,q);
	print(p1);
//	if(p->data>q->data)
//		cout<<p->data;

}