C语言链表在笔试面试中常考问题总结

发布时间:2014-10-22 14:44:37编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"C语言链表在笔试面试中常考问题总结",主要涉及到C语言链表在笔试面试中常考问题总结方面的内容,对于C语言链表在笔试面试中常考问题总结感兴趣的同学可以参考一下。

1、实现单链表逆置    无头结点: 1 #include<stdio.h>  2 #include<stdlib.h>  3   4 typedef struct node{  5     int data;  6     struct node *next;  7 }Node;  8   9 //创建链表 10 Node *CreateList(void){ 11     int val,i,n; 12     Node *head,*p,*q; 13  14     head=NULL; 15     printf("请输入您要建立的链表长度:\n");   16     scanf("%d",&n); 17     printf("请输入您要输入的数据:\n");   18     for(i=0;i<n;i++){ 19         scanf("%d",&val); 20         p=(Node*)malloc(sizeof(Node)); 21         p->data=val; 22         if(head==NULL) 23             head=q=p; 24         else 25             q->next=p; 26         q=p; 27    } 28     p->next=NULL; 29     return head; 30 } 31  32 //链表的逆置 33 Node *ReverseList(Node *head){ 34     Node *p,*q,*r; 35     p=head; 36     q=r=NULL; 37     while(p){ 38         q=p->next; 39         p->next=r; 40         r=p; 41         p=q; 42    } 43     return r; 44 } 45  46 //输出链表 47 void ShowList(Node *head){ 48     Node *p; 49     p=head; 50     while(p){ 51         printf("%d ",p->data); 52         p=p->next; 53    } 54     printf("\n"); 55 } 56  57 void main(){ 58     Node *head; 59  60     head=CreateList(); 61     printf("链表逆置前的数据:\n"); 62    ShowList(head); 63  64     head=ReverseList(head); 65     printf("链表逆置后的数据:\n");   66    ShowList(head);   67 }   2、判断单链表是否有环   判断链表是否存在环的办法为:   设置两个指针(fast,slow),初始值都指向头指针,slow每次前进一步,fast每次前进两步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行从头到尾部为NULL,则为无环链表)程序如下: 1 #include<stdio.h>  2 #include<stdlib.h>  3   4 typedef struct node{  5     int elem;  6     struct node * next;  7 }Node, *NodeList;  8  9 bool IsExitsLoop(NodeList head){ 10     NodeList slow=head,fast=head; 11     while(fast && fast->next){ 12         slow=slow->next; 13         fast=fast->next->next; 14         if(slow==fast) 15             break; 16    } 17     return !(fast==NULL || fast->next==NULL); 18 } 19  20 void main(){ 21     //创建一个有环的单链表 22     NodeList head=NULL,p,q; 23     for(int i=1;i<=5;i++){ 24         p=(NodeList)malloc(sizeof(Node)); 25         p->elem=i; 26         if(head==NULL) 27             head=q=p; 28         else 29             q->next=p; 30         q=p; 31    } 32     p=(NodeList)malloc(sizeof(Node)); 33     p->elem=6; 34     q->next=p; 35     q=p; 36     q->next=head->next->next->next; 37     //判断单链表是否存在环 38     printf("单链表是否存在环: "); 39     bool b=IsExitsLoop(head); 40     printf("%s\n",b==false?"false":"true"); 41 }   3、如果单链表有环,则找到环的入口点   当fast若与slow相遇时,slow肯定没有遍历完链表,而fast已经在环内循环了n圈(1<=n),假设slow走了s步,而fast走了2s步(fast步数还等于s加上在环上多转的n圈),设环长为r,则:     2s = s + n*r;     s = n*r; 设整个链表长为L,入口环与相遇点距离为x,起点到环入口点的距离为a。     a + x = n*r;     a + x = (n-1)*r + r = (n-1)*r + L -a; a = (n-1)r + (L – a – x); (L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下: 1 #include<stdio.h>  2 #include<stdlib.h>  3   4 typedef struct node{  5     int elem;  6     struct node * next;  7 }Node, *NodeList;  8   9 //寻找环的入口点 10 NodeList FindLoopPort(NodeList head){ 11     NodeList slow=head,fast=head; 12     while(fast && fast->next){ 13         slow=slow->next; 14         fast=fast->next->next; 15         if(slow==fast) 16             break; 17    } 18     if(fast==NULL||fast->next==NULL) 19         return NULL; 20     slow=head; 21     while(slow!=fast){ 22         slow=slow->next; 23         fast=fast->next; 24    } 25     return slow; 26 } 27  28 void main(){ 29     //创建一个有环的单链表 30     NodeList head=NULL,p,q; 31     for(int i=1;i<=5;i++){ 32         p=(NodeList)malloc(sizeof(Node)); 33         p->elem=i; 34         if(head==NULL) 35             head=q=p; 36         else 37             q->next=p; 38         q=p; 39    } 40     p=(NodeList)malloc(sizeof(Node)); 41     p->elem=6; 42     q->next=p; 43     q=p; 44     q->next=head->next->next->next; 45     //寻找环的入口点 46     NodeList list=FindLoopPort(head); 47     printf("环的入口节点元素值为:%d\n",list->elem); 48 }   4、判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)   比较好的方法有两个:   一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。   二、如果两个链表相交,那么两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。


上一篇:ZOJ 3690
下一篇:TopCoder SRM 590 Div2 第3题

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款