常见面试题之链表操作

一、链表创建

链表主要有三种形式，包括单链表、双链表和循环链表。 单链表每个节点只包含一个后驱指针，双链表节点同时包含一个前驱指针和一个后驱指针，循环链表的尾节点的后驱指向头节点。 代码如下：

/插入节点/

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) coutelem; 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;

}

/求中间节点/ 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; }

/合并有序单链表/ 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->elemelem)/链表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; }

“`