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

1、实现单链表逆置

　　无头结点：

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefstructnode{

5intdata;

6structnode*next;

7}Node;

8

9//创建链表

10Node*CreateList(void){

11intval,i,n;

12Node*head,*p,*q;

13

14head=NULL;

15printf("请输入您要建立的链表长度:\n");

16scanf("%d",&n);

17printf("请输入您要输入的数据:\n");

18for(i=0;i<n;i++){

19scanf("%d",&val);

20p=(Node*)malloc(sizeof(Node));

21p->data=val;

22if(head==NULL)

23head=q=p;

24else

25q->next=p;

26q=p;

27}

28p->next=NULL;

29returnhead;

30}

31

32//链表的逆置

33Node*ReverseList(Node*head){

34Node*p,*q,*r;

35p=head;

36q=r=NULL;

37while(p){

38q=p->next;

39p->next=r;

40r=p;

41p=q;

42}

43returnr;

44}

45

46//输出链表

47voidShowList(Node*head){

48Node*p;

49p=head;

50while(p){

51printf("%d",p->data);

52p=p->next;

53}

54printf("\n");

55}

56

57voidmain(){

58Node*head;

59

60head=CreateList();

61printf("链表逆置前的数据:\n");

62ShowList(head);

63

64head=ReverseList(head);

65printf("链表逆置后的数据:\n");

66ShowList(head);

67}

2、判断单链表是否有环

　　判断链表是否存在环的办法为：

　　设置两个指针(fast,slow)，初始值都指向头指针，slow每次前进一步，fast每次前进两步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。（当然，fast先行从头到尾部为NULL，则为无环链表）程序如下：

1#include<stdio.h>

2#include<stdlib.h>

3

4typedefstructnode{

5intelem;

6structnode*next;

7}Node,*NodeList;

8

9boolIsExitsLoop(NodeListhead){

10NodeListslow=head,fast=head;

11while(fast&&fast->next){

12slow=slow->next;

13fast=fast->next->next;

14if(slow==fast)

15break;

16}

17return!(fast==NULL||fast->next==NULL);

18}

19

20voidmain(){

21//创建一个有环的单链表

22NodeListhead=NULL,p,q;

23for(inti=1;i<=5;i++){

24p=(NodeList)malloc(sizeof(Node));

25p->elem=i;

26if(head==NULL)

27head=q=p;

28else

29q->next=p;

30q=p;

31}

32p=(NodeList)malloc(sizeof(Node));

33p->elem=6;

34q->next=p;

35q=p;

36q->next=head->next->next->next;

37//判断单链表是否存在环

38printf("单链表是否存在环:");

39boolb=IsExitsLoop(head);

40printf("%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

4typedefstructnode{

5intelem;

6structnode*next;

7}Node,*NodeList;

8

9//寻找环的入口点

10NodeListFindLoopPort(NodeListhead){

11NodeListslow=head,fast=head;

12while(fast&&fast->next){

13slow=slow->next;

14fast=fast->next->next;

15if(slow==fast)

16break;

17}

18if(fast==NULL||fast->next==NULL)

19returnNULL;

20slow=head;

21while(slow!=fast){

22slow=slow->next;

23fast=fast->next;

24}

25returnslow;

26}

27

28voidmain(){

29//创建一个有环的单链表

30NodeListhead=NULL,p,q;

31for(inti=1;i<=5;i++){

32p=(NodeList)malloc(sizeof(Node));

33p->elem=i;

34if(head==NULL)

35head=q=p;

36else

37q->next=p;

38q=p;

39}

40p=(NodeList)malloc(sizeof(Node));

41p->elem=6;

42q->next=p;

43q=p;

44q->next=head->next->next->next;

45//寻找环的入口点

46NodeListlist=FindLoopPort(head);

47printf("环的入口节点元素值为：%d\n",list->elem);

48}

4、判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）

　　比较好的方法有两个：

　　一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

　　二、如果两个链表相交，那么两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。