常見面試題之鏈表操作

鏈表的常見操作

鏈表是數據結構的重要內容在計算機程序中應用廣泛同時也是各公司筆試題目的重點

　　以下簡單實現了鏈表的一些操作包括創建增加節點刪除節點單鏈表逆置合並有序鏈表等

一鏈表創建

　　鏈表主要有三種形式包括單鏈表雙鏈表和循環鏈表

　　單鏈表每個節點只包含一個後驅指針雙鏈表節點同時包含一個前驅指針和一個後驅指針循環鏈表的尾節點的後驅指向頭節點

　　代碼如下

/*單鏈表節點結構*/
typedef struct NodeType
{
char elem;
NodeType*next;
}Node;

/*雙鏈表節點結構*/
typedef struct 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()
{
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;
}

/*創建雙鏈表*/
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()
{
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;
}

/*創建循環鏈表*/
Node* CycleList(Node*head)
{
if(NULL== head)/*分配頭節點空間*/
head=(Node*)malloc(sizeof(Node))head>next=NULL;

Node*current=head *temp;
char ch;

while()
{
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;
}

二鏈表操作

　　包括單鏈表的增加節點刪除節點輸出鏈表等

添加節點

/*插入節點*/

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;

}

/*
輸出鏈表
*/
void PrintList(Node*head)
{
Node* current=head>next;
cout<<&#;\n List are:&#;;
while(NULL!= current)
{
if(NULL!= current>elem)
cout<<setw()<<current>elem;
current=current>next;
}

cout<<&#;\n&#;;
}

三單鏈表逆置

　　單鏈表逆置在各公司的筆試題中比較常見以下是其中一種實現

　　算法描述將鏈表中每一個節點插入到頭結點之後

　　代碼如下

單鏈表逆置/*單鏈表逆置*/
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;

}

四求單鏈表中間節點

　　在筆試題中比較常見通常題目描述是給出一個單鏈表不知道節點N的值怎樣只遍歷一次就可以求出中間節點

　　算法描述設立兩個指針ppp每次移動個節點位置p每次移動個節點位置當p移動到尾節點時p指向中間節點

　　代碼如下

求中間節點

/*求中間節點*/
Node* MiddleNode(Node*head)
{
if(NULL== head)
return head;
if(NULL== head>next)
return head>next;

Node*p*p;
p=head;
p=head;

while(p>next)
{
/*p節點移動個節點位置*/
p=p>next;
if(p>next)/*判斷p後驅節點是否存在存在則再移動一次*/
p=p>next;
/*p節點移動個節點位置*/
p=p>next;

}
return p;

}

五合並有序單鏈表

　　問題描述合並個有序單鏈表合並後的鏈表也是排好序的

　　算法描述對鏈表A中的每一個節點元素查找其在鏈表B中的插入位置並在B中插入該元素

　　代碼如下

合並有序單鏈表/*合並有序單鏈表*/
Node* MergeList(Node* hNode* h)
{
if(NULL== h|| NULL== h)
return h;
if(NULL== h>next )
return h;
if(NULL== h>next)
return h;

Node* curr*curr*prev*temp;
prev=h;/*鏈表的前驅節點*/
curr=h>next;/*鏈表的當前節點*/
curr=h>next;/*鏈表的當前節點*/
temp=h;
while(curr)
{
while(curr&& curr>elem< curr>elem)/*鏈表指針移動至大或等於鏈表當前元素的位置*/
prev=currcurr=curr>next;

/*在鏈表中插入鏈表的當前元素*/
temp=curr>next;/*暫存鏈表的下一個節點*/
prev>next=curr;
curr>next=curr;

/*鏈表移動至新節點*/
curr=curr;
/*鏈表移動至下一個節點*/
curr=temp;
}

return h;

}

六判斷鏈表是否有環

　　判斷鏈表是否有環即是判斷鏈表是否為循環鏈表算法較為簡單一次遍歷判斷尾指針是否指向頭指針即可

　　代碼如下

/*判斷鏈表是否有環(循環鏈表)*/
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;
}

七總結

　　以上實現了鏈表的一些常見操作源文件LinkListcpp全部代碼如下

/*
* 作者 達聞東
* 修改日期 :
* 描述 實現鏈表的常見操作
*
*/
#include<iostream>
#include<iomanip>
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()
{
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<<setw()<<current>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*headchar 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*p*p;
p=head;
p=head;

while(p>next)
{
/*p節點移動個節點位置*/
p=p>next;
if(p>next)/*判斷p後驅節點是否存在存在則再移動一次*/
p=p>next;
/*p節點移動個節點位置*/
p=p>next;

}
return p;

}

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

/*合並有序單鏈表*/
Node* MergeList(Node* hNode* h)
{
if(NULL== h|| NULL== h)
return h;
if(NULL== h>next )
return h;
if(NULL== h>next)
return h;

Node* curr*curr*prev*temp;
prev=h;/*鏈表的前驅節點*/
curr=h>next;/*鏈表的當前節點*/
curr=h>next;/*鏈表的當前節點*/
temp=h;
while(curr)
{
while(curr&& curr>elem< curr>elem)/*鏈表指針移動至大或等於鏈表當前元素的位置*/
prev=currcurr=curr>next;

/*在鏈表中插入鏈表的當前元素*/
temp=curr>next;/*暫存鏈表的下一個節點*/
prev>next=curr;
curr>next=curr;

/*鏈表移動至新節點*/
curr=curr;
/*鏈表移動至下一個節點*/
curr=temp;
}

return h;

}

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

/*創建雙鏈表*/
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()
{
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<<setw()<<p>elem;

}

cout<<&#;\n DoubleList are:&#;;
while(p>prev)
{
if(p>elem)
cout<<setw()<<p>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()
{
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* head*head;
DNode* dHead;
char ch;
head= NULL;
head=NULL;
head=NULL;
dHead=NULL;

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

//創建單鏈表
head=CreateList(head);
PrintList(head);

head=CreateList(head);
PrintList(head);

//插入節點

cout<<&#;\n input elem to insert:&#;;
cin>>ch;
InsertNode(headch);
PrintList(head);

//刪除節點

cout<<&#;\n input elem to delete:&#;;
cin>>ch;
DeleteNode(headch);
PrintList(head);

//單鏈表逆置

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

//求中間節點

p=MiddleNode(head);
cout<<&#;\n Middle Node is:&#;;
cout<<p>elem<<endl;

//合並有序單鏈表

MergeList(headhead);
cout<<&#;\n Merged!&#;;
PrintList(head);

//創建雙鏈表

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

/*創建循環鏈表並判斷是否有環*/
head=CycleList(head);
cout<<IsCycleList(head);
return ;
}

From:http://tw.wingwit.com/Article/program/sjjg/201404/30581.html