有序单链表的合并

已知连个链表head1和head2各自有序，请把他们合并成一个链表并且其依然有序。

分别使用非递归和递归方法实现。

 

1  非递归方式：

// 单链表.cpp : 定义控制台应用程序的入口点。
//单链表
#include "stdafx.h"
#include <iostream>
#include <complex>
using namespace std;

typedef struct node {
int data;//节点内容
node *next;//下一个节点
}node;

//单链表的正向排序
node *InsertSort(){
node *head,*p,*q,*cur;
int a=-1;
head=new node;
head->next=NULL;
while (1)
{
cout<<"please input the data(-1,quit):";
cin>>a;
if (-1==a){ //输入-1结束
break;
}
p=new node;
p->data=a;
p->next=NULL;
q=head->next;
if (q==NULL){//如果第一个节点为NULL，则对第一个节点赋值
head->next=p;
continue;
}
if (q->data>a){//如果插入值小于第一个节点，则插入到head之后
p->next=head->next;
head->next=p;
}
else{    //如果插入值大于等于第一个节点
while (q->data<a){
cur=q;
q=q->next;
if (q==NULL){ //如果到了末尾，则跳出循环
break;
}
}
if (q==NULL){ //如果到了末尾,直接插入到末节点后面
cur->next=p;
}
p->next=q; //插入值插到q前面，cur后面
cur->next=p;
}
}
return head;
}

//两个有序单链表进行合并
node *merge(node *head1,node *head2){
if (head1==NULL || head1->next==NULL)
{
return head2;
}
if (head2==NULL || head2->next==NULL)
{
return head1;
}
node *head; //合并后的头指针
    head=new node; 
head->next=NULL;
node *p,*q;
node *p1=head1->next;//p1指向head1的第一个节点
node *p2=head2->next;//p2指向head2的第二个节点
  q=head;//q指向合并后的单链表
while (p1!=NULL && p2!=NULL){
if (p1->data<=p2->data){ //如果p1指向的节点值小则插入其对应值
p=new node;
p->next=NULL;
p->data=p1->data;
q->next=p;
q=q->next; //q指向新末节点
p1=p1->next;//p1 指向下一个节点
}
else{ //否则插入p2指向节点对应值
p=new node;
p->data=p2->data;
p->next=NULL;
q->next=p;
q=q->next;//q指向新末节点
p2=p2->next;//p2 指向下一个节点
}
}

if (p1!=NULL) //如果p1指向的单链表没有插入完，则把剩余的插入到q的后面
{
while (p1!=NULL)
{
p=new node;
p->data=p1->data;
p->next=NULL;
q->next=p;
q=q->next;
p1=p1->next;
}
}
if (p2!=NULL)//如果p2指向的单链表没有插入完，则把剩余的插入到q的后面
{
while (p2!=NULL)
{
p=new node;
p->data=p2->data;
p->next=NULL;
q->next=p;
    q=q->next;
p2=p2->next;
}
}
return head; //返回合并后单链表的头指针
}

//打印单链表
void print(node *head){
node *p=head->next;
int index=0;
if (p==NULL)//链表为NULL
{
cout<<"Link is empty!"<<endl;
getchar();
return;
}
while (p!=NULL)//遍历链表
{
cout<<"The "<<++index<<"th node is :"<<p->data<<endl;//打印元素
p=p->next;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
node *head1=InsertSort();//创建单链表
node *head2=InsertSort();//创建单链表
node *head=merge(head1,head2);
cout<<"after merge:"<<endl;
print(head);
system("pause");
delete [] head1;
delete [] head2;
delete [] head;
return 0;
}