rr2)
{
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;
}
六、判断链表是否有环
判断链表是否有环即是判断链表是否为循环链表，算法较为简单，一次遍历判断尾指针是否指向头指针即可。
代码如下：
/*判断链表是否有环(循环链表)*/
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;
}
七、总结
以上实现了链表的一些常见操作，源文件LinkList.cpp全部代码如下：
/*
* 作者： 达闻东
* 修改日期： 2010-04-28 17:10
* 描述： 实现链表的常见操作
*
*/
#include
#include
using namespace std;
/*单链表节点结构*/
typedefstruct NodeType
{
char elem;
NodeType*next;
}Node;
/*双链表节点结构*/
typedefstruct DNodeType
{
char elem;
DNodeType*next;
DNodeType*prev;
}DNode;
/*=============================================================================*/
/*
创建链表
*/
Node* CreateList(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;/*当前节点为链表尾节点*/
}
return head;
}
/*=============================================================================*/
/*
输出链表
*/
void PrintList(Node*head)
{
Node* current=head->next;
cout<<”\n List are:”;
while(NULL!= current)
{
if(NULL!= current->elem)
cout<elem;
current=current->next;
}
cout<<”\n”;
}
/*=============================================================================*/
/*插入节点*/
Node*InsertNode(Node*head ,char elem)
{
if( NULL== head|| NULL== elem )
return head;
Node*current=head->next;/*当前节点*/
Node*prev=head;/*前驱节点*/
Node*temp;/*过渡节点*/
while(current)/*移动至尾节点*/
{
prev=current;
current=current->next;
}
temp=(Node*) malloc(sizeof(Node) );
temp->elem=elem;
temp->next=NULL;
prev->next=temp;/*尾节点的后驱指向新节点*/
return head;
}
/*=============================================================================*/
/*删除节点*/
Node*DeleteNode(Node*head,char elem)
{
if(NULL== head|| NULL== elem)
return head;
if(NULL== head->next)
return head;
Node*prev,*current;
prev=head;
current=head->next;
while(current)
{
if(current->elem== elem)/*匹配节点元素*/
{
prev->next=current->next;/*前驱节点的后驱指向当前节点的下一个节点*/
free(current);/*释放当前节点*/
return head;
}
prev=current;
current=current->next;/*移动至下一个节点*/
}
return head;
}
/*=============================================================================*/
/*单链表逆置*/
Node*ReverseList(Node*head)
{
if(NULL== head)
return head;
if(NULL== head->next)
return head;
if(NULL== head->next->next)
return head;
Node*curr=head->next;/*当前节点*/
head->next=NULL;
Node*temp;
while(curr)
{
temp=curr->next;/*暂存下一个节点*/
/*把当前节点插入到head节点后*/
curr->next=head->next;
head->next=curr;
curr=temp;/*移动至下一个节点*/
}
return head;
}
/*=============================================================================*/
/*求中间节点*/
Node* MiddleNode(Node*head)
{
if(NULL== head)
return head;
if(NULL== head->next)
return head->next;
Node*p1,*p2;
p1=head;
p2=head;
while(p2->next)
{
/*p2节点移动2个节点位置*/
p2=p2->next;
if(p2->next)/*判断p2后驱节点是否存在，存在则再移动一次*/
p2=p2->next;
/*p1节点移动1个节点位置*/
p1=p1->next;
}
return p1;
}
/*====================