C语言实现判断单链表中是否有环_给定如下单链表l,l为头指针,判断该链表是否局部存在环

C语言实现判断单链表中是否有环

判断单链表中是否存在环的两种思路

1. 计算步数

   思路：定义两个指针p,q，都指向头结点，p一直后移，q每次后移到和p相同的结点，判断p是否等于q，不等于则p继续后移，q重新头结点开始计数，循环中，分别用两个变量记录循环的次数，当p==q，而两个步数变量却不相等时，说明p指针已经经过回环一次，说明链表中存在环。

2. 快慢指针

   确定环入口思路：
   
   第一步找出两个指针的相遇点，第二步让快指针从相遇点开始走，让慢指针从链表的最开始走，快慢指针每次各走一步，当两个指针相遇了，即是入口点。

在相遇点，slow走的路程是L+X，fast走的是L+X+C(C是回环周长)，快指针fast速度时慢指针的2倍，所以又2（L+X）= L+X+C,所以L = C - X；此时让慢指针slow从新从头结点开始走，走到环入口的位置为L，快指针fast改一次走一步，当slow走到环入口，此时快慢指针相遇点到达环入口的距离=C - X ，即为L，所以当slow走到环入口，fast刚好也到环入口，指针相遇，也刚好是环入口。

代码实现

data.h

/*
 * @Author: xgh
 * @Date: 2020-05-30 08:01:30
 * @LastEditTime: 2020-06-14 14:31:32
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \VS-CODE-C\.vscode\singlyLinkedLists\data.h
 */ 

#ifndef __DATA_H__
#define __DATA_H__

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SUCCESS 1  //成功
#define FAILURE 0  //失败
#define ERROR 0 //错误

typedef int Statue;  // 为int取别名，用于区分表示执行状态的int
typedef int ElemType;  // 数据域类型

// 链表结构体:结点（数据域+指针域）
typedef struct Node
{
    ElemType data; //数据域

    // 这里不能写成Node *next
    // 因为类型名的作用域是从大括号结尾开始，而在结构体内部不能使用，因为还没有定义
    // 需要声明
    struct Node *next;  // 指针域
}node; 

// 使用*LinkList而不直接使用node的原因为：
// 节省空间, 无论node中的data有多大, LinkList只占一个指针变量大小
typedef struct Node *LinkList;
/*
 * 上方结构体定义可用以下两种定义方式替换：
 * 
 * 方法1：
 * struct Node;
 * typedef struct Node node;
 *
 * struct Node
 * {
 *    ElemType data; // 数据域
 *    Node *next; // 指针域
 * };
 * 
 * 方法2：
 * typedef struct Node
 * {
 *    ElemType data; //数据域
 *    struct Node *next; // 指针域
 * };
 * 
 * typedef struct Node node;
 */

#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

测试代码：

/*
 * @Author: xgh
 * @Date: 2020-06-14 14:18:08
 * @LastEditTime: 2020-06-14 22:39:38
 * @LastEditors: Please set LastEditors
 * @Description: 判断单链表中是否带环
 * @FilePath: \VS-CODE-C\.vscode\loopSinglyLinkedLists\loopSilnglyLinkedLists.c
 */ 
#include "data.h"

Statue GreateListTail(LinkList *L, int n);
Statue GetLength(LinkList L);
void ListElemOutput(LinkList L);
Statue setLoopLinkList(LinkList L, int loop_pos);
int isLoopLinkList_01(LinkList L);
int isLoopLinkList_02(LinkList L);

int main(void){

    LinkList list = NULL;
    GreateListTail(&list, 6);
    printf("表长度为：%d\n", GetLength(list));

    ListElemOutput(list);

    if(setLoopLinkList(list, 4)){
        printf("快慢指针方式,环入口为第%d个结点\n\n", isLoopLinkList_01(list));
        printf("记步数方式,环入口为第%d个结点\n\n", isLoopLinkList_02(list));
    }
    
    return 0;

}

/**
 * @description: 输出表内容
 * @param {LinkList L: 结构体一级指针} 
 * @return: NULL
 */
void ListElemOutput(LinkList L)
{
    LinkList p = L->next;
    printf("当前表数据为:");
    while(p){
        printf("%4d", p->data);
        p = p->next;
    }

    printf("\n");
}

/**
 * @description: 获取表长度
 * @param {LinkList L：结构体指针} 
 * @return: 表长度
 */
Statue GetLength(LinkList L)
{

    int length = 0; // 保存表长度变量
    LinkList p = L->next;  // 获取头结点的下一个结点地址

    while (p != NULL) // 结点指针域不为NULL, 说明有数据
    {
        length++; // 长度加1
        p = p->next; // 获取下一个结点地址
    }
    
    // 返回结果
    return length;
}

/**
 * @description: 尾插法创建链表, 数据域data存放随机数[1, 100]
 * @param {LinkList *L:结构体二级指针} 
 * @param {int n: 插入数据的个数}
 * @return: FAILUER: 内存分配失败
 * @return: SUCCESS: 插入成功
 */
Statue GreateListTail(LinkList *L, int n)
{
    LinkList r, s;
    int i;

    srand(time(0)); // 初始化随机数种子
    //获取头指针
    *L = (LinkList) malloc (sizeof(node));
    if(*L == NULL){
        printf("内存分配失败\n\n");
        return FAILURE;
    } 

    r = *L;  // 将内存分配的头指针给到r

    for(i = 0; i < n; i++){
        s = (LinkList) malloc (sizeof(node));  // 新结点
        s->data = rand() % 100 + 1;  // rand()生成随机数, 对100取模, 生成[0, 99]的数, 加1生成[1, 100]

        r->next = s; // r指向新结点
        r = s; //将r移动到新结点, 即现在r为新结点
    }

    r->next = NULL; // 表尾
    return SUCCESS;
}

/**
 * @description: 设置带环的单链表
 * @param {LinkList L:一级指针} 
 * @param {int loop_pos:构建环的位置}
 * @return: ERROR: 数据错误
 * @return：SUCCESS: 设置成功
 */
Statue setLoopLinkList(LinkList L, int loop_pos){

    // 判断链表是否为空或者构建回环的位置是否正确
    if(L == NULL || GetLength(L) == 0 || loop_pos >= GetLength(L)){
        return ERROR;
    }
    // 头结点
    LinkList node = L;
    // 第loop_pos位置的结点
    LinkList loop_node = NULL;

    int i = 0;

    // 循环判断, 到表尾退出
    while(1){
        // 判断是否到达表尾
        if(node->next != NULL){

            // 未到达表尾, 则结点后移
            node = node->next;
            i++; // 结点数加1

            // 判断是否到达设置回环的结点
            if(i == loop_pos){
                // 获取该结点
                loop_node = node;
            }

        }else{  // 到达表尾退出

            break;
        }
    }

    // 循环结束, 此时node为表尾结点, 将它的指针域指向回环的结点
    node->next = loop_node;

    printf("单链表回环设置成功\n\n");
    return SUCCESS;

}

/**
 * @description: 判断单链表是否是带环(快慢指针方式)
 * @param {LinkList L: 一级指针} 
 * @return: 环的位置
 * @return: ERROR: 数据错误或没有环
 */
int isLoopLinkList_01(LinkList L){
    if(L == NULL || L->next == NULL){
        printf("表错误\n\n");
        return ERROR;
    }

    LinkList slow = L; // 慢指针
    LinkList fast = L; // 快指针

    int pos = 0; // 相遇标志
    int loop_In = 0;  // 到环入口的结点数

    // 判断有没有环
    while(fast != NULL && fast->next != NULL ){
        fast = fast->next->next;
        slow = slow->next;

        // 快慢指针是相遇
        if(fast == slow){
            pos = 1;
            break; // 跳出循环
        }
    }

    // 在有环的基础上找到第一个入口
    if(pos == 1){
        fast = L; // 快指针从头开始走,且这次一次只后移一个结点

        // 快慢指针是否相遇
        while(fast != slow){
            // 快慢指针后移一个结点
            fast = fast->next;
            slow = slow->next;
            loop_In++;
        }

        printf("快慢指针的方式,环入口的结点数据为%d\n\n", slow->data);
        return loop_In;
    }

    return ERROR;

}

/**
 * @description: 判断单链表是否是带环(计算步数方式)
 * @param {LinkList L: 一级指针} 
 * @return: 环的位置
 * @return: ERROR: 数据错误或没有环
 */
int isLoopLinkList_02(LinkList L){

    int count_01 = 0, count_02;  // 计算两个指针的步数
    LinkList p1 = L, p2;

    while(p1)
    {
        count_02 = 0;  // 每次指针p1后移一个结点, 指针p2都从新计数
        p2 = L;

        // 每次指针p2重新走一次, 走到指针p1的位置
        while(p2 && (p1 != p2)){

            p2 = p2->next;
            count_02++;
        }

        // 判断是不是有环, 有环则是屏p1 == p2, 且步数不一样
        if(p1 == p2 && (count_01 != count_02)){
            printf("记步数的方式,环入口的结点数据为%d\n\n", p2->data);
            return count_02;
        }

        // 指针p1往后移一个结点, 步数加一
        p1 = p1->next;
        count_01++;
    }

    return ERROR;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241