/*合并有序单链表*/
Node* MergeList(Node* h1,Node* h2)
{
if(NULL== h1|| NULL== h2)
return h1;
if(NULL== h1->next )
return h2;
if(NULL== h2->next)
return h1;

Node* curr1,*curr2,*prev1,*temp;
prev1=h1;/*链表1的前驱节点*/
curr1=h1->next;/*链表1的当前节点*/
curr2=h2->next;/*链表2的当前节点*/
temp=h2;
while(curr2)
{
while(curr1&& curr1->elem< curr2->elem)/*链表1指针移动至大或等于链表2当前元素的位置*/
prev1=curr1,curr1=curr1->next;

/*在链表1中插入链表2的当前元素*/
temp=curr2->next;/*暂存链表2的下一个节点*/
prev1->next=curr2;
curr2->next=curr1;

/*链表1移动至新节点*/
curr1=curr2;
/*链表2移动至下一个节点*/
curr2=temp;
}

return h1;

}

/*=============================================================================*/

/*创建双链表*/
DNode* DoubleList(DNode*head)
{
if(NULL== head)//分配头节点空间
head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL , head->next=NULL;

DNode*current=head ,*temp;
char ch;

while(1)
{
cout<<”\n input elem:”;
cin>>ch;
if(‘#’ == ch)/*#结束输入*/
break;
temp=(DNode*) malloc (sizeof(DNode) );
temp->elem=ch;
temp->next=NULL;
current->next=temp;/*当前节点的后驱指向新节点*/
temp->prev=current;/*新节点的前驱指向当前节点*/
current=temp;/*当前节点为链表尾节点*/

}

return head;
}

/*=============================================================================*/
/*输出双链表*/
void PrintDoubleList(DNode*head)
{
if(NULL== head)
return;

DNode* p;
p=head;
cout<<”\n DoubleList are:”;
while(p->next)
{
p=p->next;
if(p->elem)
cout<elem;

}

cout<<”\n DoubleList are:”;
while(p->prev)
{
if(p->elem)
cout<elem;
p=p->prev;
}

}

/*=============================================================================*/
/*创建循环链表*/
Node* CycleList(Node*head)
{
if(NULL== head)/*分配头节点空间*/
head=(Node*)malloc(sizeof(Node)),head->next=NULL;

Node*current=head ,*temp;
char ch;

while(1)
{
cout<<”\n input elem:”;
cin>>ch;
if(‘#’ == ch)/*#结束输入*/
break;
temp=(Node*) malloc (sizeof(Node) );
temp->elem=ch;
temp->next=NULL;
current->next=temp;/*当前节点的后驱指向新节点*/
current=temp;/*当前节点为链表尾节点*/

}
current->next=head;/*尾节点指向头节点*/
return head;
}
/*=============================================================================*/

/*判断链表是否有环(循环链表)*/
bool IsCycleList(Node*head)
{
if(NULL== head)
return false;
if(NULL== head->next)
return false;
Node*current=head->next;
while(current)
{
if(head== current->next)
return true;
current=current->next;
}
return false;
}
int main()
{
Node* head,*p;
Node* head2,*head3;
DNode* dHead;
char ch;
head= NULL;
head2=NULL;
head3=NULL;
dHead=NULL;

//head=(Node*) malloc ( sizeof( Node) );
//head->next = NULL;

//创建单链表
head=CreateList(head);
PrintList(head);

head2=CreateList(head2);
PrintList(head2);

//插入节点

cout<<”\n input elem to insert:”;
cin>>ch;
InsertNode(head,ch);
PrintList(head);

//删除节点

cout<<”\n input elem to delete:”;
cin>>ch;
DeleteNode(head,ch);
PrintList(head);

//单链表逆置

head=ReverseList(head);
cout<<”\n Reversed !”;
PrintList(head);

//求中间节点

p=MiddleNode(head);
cout<<”\n Middle Node is:”;
cout<elem<

//合并有序单链表

MergeList(head,head2);
cout<<”\n Merged!”;
PrintList(head);

//创建双链表

dHead=DoubleList(dHead);
PrintDoubleList(dHead);

/*创建循环链表并判断是否有环*/
head3=CycleList(head3);
cout< return 0;
}