C语言如何判断链表里是否有环

创作时间:

作者:

@小白创作中心

C语言如何判断链表里是否有环

引用

来源

https://docs.pingcode.com/baike/1208193

在C语言中，判断链表是否有环是一个常见的编程问题。本文将介绍三种常用的方法：快慢指针法、哈希表法和修改链表结构法，并通过详细的步骤说明和示例代码帮助读者理解这些方法的实现原理。

快慢指针法

快慢指针法，也称为龟兔赛跑算法，是判断链表中是否存在环的经典方法。其核心思想是利用两个指针以不同的速度遍历链表。

具体步骤

初始化两个指针：慢指针（slow）和快指针（fast），都指向链表的头节点。
在链表中进行遍历：

慢指针每次移动一个节点。
快指针每次移动两个节点。

如果快指针与慢指针相遇，则说明链表中存在环。
如果快指针移动到链表的末尾（即指向 NULL），则说明链表中没有环。

示例代码

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

struct ListNode {
    int val;
    struct ListNode *next;
};

int hasCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return 1; // 有环
        }
    }
    return 0; // 无环
}

int main() {
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = head; // 创建一个有环的链表
    int result = hasCycle(head);
    if (result) {
        printf("链表中有环\n");
    } else {
        printf("链表中无环\n");
    }
    free(head);
    return 0;
}

哈希表法

哈希表法利用哈希表来存储已访问的节点地址，从而检测链表中是否存在环。这种方法的时间复杂度为O(n)，但需要额外的空间来存储节点地址。

具体步骤

初始化一个哈希表。
遍历链表中的每个节点：

如果节点的地址已经存在于哈希表中，则说明链表中存在环。
如果节点的地址不在哈希表中，则将该节点地址存入哈希表。

如果遍历结束后没有发现重复的节点地址，则说明链表中没有环。

示例代码

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct HashNode {
    struct ListNode *key;
    UT_hash_handle hh;
};

int hasCycle(struct ListNode *head) {
    struct HashNode *visited = NULL, *tmp;
    while (head != NULL) {
        HASH_FIND_PTR(visited, &head, tmp);
        if (tmp != NULL) {
            return 1; // 有环
        }
        tmp = (struct HashNode*)malloc(sizeof(struct HashNode));
        tmp->key = head;
        HASH_ADD_PTR(visited, key, tmp);
        head = head->next;
    }
    // 释放哈希表
    HASH_ITER(hh, visited, tmp, tmp) {
        HASH_DEL(visited, tmp);
        free(tmp);
    }
    return 0; // 无环
}

int main() {
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = head; // 创建一个有环的链表
    int result = hasCycle(head);
    if (result) {
        printf("链表中有环\n");
    } else {
        printf("链表中无环\n");
    }
    free(head);
    return 0;
}

修改链表结构法

修改链表结构法通过修改链表节点的结构来标记已访问的节点，从而判断链表中是否存在环。这种方法需要修改链表节点的结构，不适用于所有场景。

具体步骤

在链表节点结构中添加一个标记位。
遍历链表中的每个节点：

如果节点的标记位已被标记，则说明链表中存在环。
如果节点的标记位未被标记，则标记该节点。

如果遍历结束后没有发现已标记的节点，则说明链表中没有环。

示例代码

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

struct ListNode {
    int val;
    struct ListNode *next;
    int visited; // 新增的标记位
};

int hasCycle(struct ListNode *head) {
    while (head != NULL) {
        if (head->visited) {
            return 1; // 有环
        }
        head->visited = 1;
        head = head->next;
    }
    return 0; // 无环
}

int main() {
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 1;
    head->next = head; // 创建一个有环的链表
    head->visited = 0;
    int result = hasCycle(head);
    if (result) {
        printf("链表中有环\n");
    } else {
        printf("链表中无环\n");
    }
    free(head);
    return 0;
}