615
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)步，之後兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。
最後更新：2017-04-03 15:21:46