c语言链表类面试题

《c语言链表类面试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本文由太阳城（http://www.tyc6600.com）提供structnode {intdata;structnode*next;};创建单链表的程序为：structnode*create(unsignedintn){//创建长度为n的单链表assert(n>0);node*head;head=newnode;head->next=NULL;cout<<"请输入head节点的值(int型)：";cin>>head->data;if(n==1){  returnhead;}node*p=head;for(unsignedinti=1;i

2、 node*tmp=newnode;  tmp->next=0;  cout<<"请输入第"<>tmp->data;  p->next=tmp;  p=tmp;}returnhead;}问题1：链表逆置思想为：head指针不断后移，指针反向即可，代码为：voidreverse(node*&head){if(head!=NULL&&head->next!=NULL){  node*p=head;  node*q=head->next;  p->next=NULL;  while(q->next!=NULL) 

3、 {   head=q->next;   q->next=p;   p=q;   q=head;  }  head->next=p;}return;}问题2：删除不知头结点链表的某个节点如果单向链表不知道头节点，一个指针指向其中的一个节点，问如何删除这个指针指向的节点？思想为：把这个节点的下一个节点的值复制给该节点，然后删除下一个节点即可。问题3：怎么判断链表中是否有环？思想为：设置两个指针，一个步长为1，另一个步长为2，依次后移，如果相遇且都不为空，则有环。与这个类似的问题包括：怎么快速检测出一个巨大的链表中的死链？或者如何找出一个单链表的中间节点？代码为

4、：boolloop(node*head){boolflag=true;if(head==NULL){  flag=false;}node*one=head;node*two=head->next;if(two==NULL){  flag=false;}while(one!=two){  if(one!=NULL)  {   one=one->next;  }  if(two!=NULL)  {   two=two->next;  }  if(two==NULL)  {   break;  }  two=two->next;  if(one==NULL

5、

6、tw

7、o==NULL)  {   break;  }}if(one==NULL

8、

9、two==NULL){  flag=false;}returnflag;}问题4：如果一个单向链表，其中有环，怎么找出这个链表循环部分的第一个节点？思想为：假设该节点在x位置处，假设步长为1的指针和步长为2的指针相遇在x+z处，循环的长度为y，那么2(x+z)-(x+z)=k*y,那么当一个指针再从开始出后移时，另一个指针从相遇点开始后移时，这两个指针就会在循环开始处相遇。代码为：node*findLoopPlace(node*head,unsignedint*place=NULL)

10、{//查找循环的位置,place存储位置if(!loop(head)){  returnNULL;}node*one=head;node*two=head->next;unsignedintcount=1;while(one!=two){   one=one->next;  two=two->next->next;}one=head;while(one!=two){    if(count!=1)  {   one=one->next;  }  two=two->next;  count++;}*place=count;returnone;}问题5：如何查找

11、链表中倒数第k个节点？思想为：两个指向头结点的指针，一个先向后移动k位，然后两个同时向后面移动直到一个节点到达链尾，前面一个指针的位置就是了。node*findLastK(node*head,unsignedintk){//查找单链表倒数第k个位置node*p=head;unsignedintcount=0;while(p!=NULL){  p=p->next;  count++;}if(countnext;}whi

12、le(p!=NULL){  q=q->next;