C语言判断链表是否有环的三种方法

C语言判断链表是否有环的三种方法

C语言判断链表是否有环的方法包括：快慢指针法、标记法、哈希表法。快慢指针法是一种高效且常用的方法，通过两个指针——一个快速移动的指针（每次走两步）和一个慢速移动的指针（每次走一步），如果链表有环，这两个指针最终会相遇。本文将详细介绍这种方法，并进一步探讨其他方法及其实现。

一、快慢指针法

快慢指针法是判断链表是否有环的经典方法。其核心思想是，通过快指针和慢指针的不同步速移动来检测环的存在。

1.1 原理

快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针。如果链表无环，快指针会到达链表末尾。

1.2 实现代码

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

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

int hasCycle(struct ListNode *head) {
    if (!head || !head->next) return 0;
    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) return 0;
        slow = slow->next;
        fast = fast->next->next;
    }
    return 1;
}

int main() {
    // 创建一个带有环的链表进行测试
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *second = malloc(sizeof(struct ListNode));
    second->val = 2;
    struct ListNode *third = malloc(sizeof(struct ListNode));
    third->val = 3;
    struct ListNode *fourth = malloc(sizeof(struct ListNode));
    fourth->val = 4;
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // 创建环
    if (hasCycle(head)) {
        printf("链表有环\n");
    } else {
        printf("链表无环\n");
    }
    // 释放内存（注意：实际项目中要小心处理环的释放问题）
    free(fourth);
    free(third);
    free(second);
    free(head);
    return 0;
}

二、标记法

标记法通过在链表遍历的过程中临时修改节点指针或使用额外字段来标记已访问的节点，以判断是否出现重复访问。

2.1 原理

在遍历链表时，将已访问的节点进行标记（例如，将节点的指针指向特殊的标记值），如果再次遇到标记节点，则说明链表存在环。

2.2 实现代码

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

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

int hasCycle(struct ListNode *head) {
    struct ListNode *marker = (struct ListNode *)0xdeadbeef; // 特殊标记
    while (head) {
        if (head == marker) return 1;
        struct ListNode *next = head->next;
        head->next = marker;
        head = next;
    }
    return 0;
}

int main() {
    // 创建一个带有环的链表进行测试
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *second = malloc(sizeof(struct ListNode));
    second->val = 2;
    struct ListNode *third = malloc(sizeof(struct ListNode));
    third->val = 3;
    struct ListNode *fourth = malloc(sizeof(struct ListNode));
    fourth->val = 4;
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // 创建环
    if (hasCycle(head)) {
        printf("链表有环\n");
    } else {
        printf("链表无环\n");
    }
    // 释放内存（注意：实际项目中要小心处理环的释放问题）
    free(fourth);
    free(third);
    free(second);
    free(head);
    return 0;
}

三、哈希表法

通过使用哈希表存储已访问的节点，在遍历过程中检测节点是否重复出现，以此判断链表是否有环。

3.1 原理

在遍历链表时，将每个访问的节点存入哈希表，如果遇到已存在于哈希表中的节点，则说明链表存在环。

3.2 实现代码

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

struct ListNode {
    int val;
    struct ListNode *next;
    struct ListNode *hashNext; // 用于哈希表的链表法解决冲突
};

#define HASH_SIZE 1024
struct ListNode *hashTable[HASH_SIZE] = {NULL};

int hashFunc(struct ListNode *node) {
    return ((uintptr_t)node) % HASH_SIZE;
}

int hasCycle(struct ListNode *head) {
    while (head) {
        int hashIndex = hashFunc(head);
        struct ListNode *current = hashTable[hashIndex];
        while (current) {
            if (current == head) return 1;
            current = current->hashNext;
        }
        head->hashNext = hashTable[hashIndex];
        hashTable[hashIndex] = head;
        head = head->next;
    }
    return 0;
}

int main() {
    // 创建一个带有环的链表进行测试
    struct ListNode *head = malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *second = malloc(sizeof(struct ListNode));
    second->val = 2;
    struct ListNode *third = malloc(sizeof(struct ListNode));
    third->val = 3;
    struct ListNode *fourth = malloc(sizeof(struct ListNode));
    fourth->val = 4;
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second; // 创建环
    if (hasCycle(head)) {
        printf("链表有环\n");
    } else {
        printf("链表无环\n");
    }
    // 释放内存（注意：实际项目中要小心处理环的释放问题）
    free(fourth);
    free(third);
    free(second);
    free(head);
    return 0;
}

四、总结

在实际项目中，我们经常需要判断链表是否有环。上述三种方法各有优缺点：

• 快慢指针法：空间复杂度低，但需要理解指针的移动规律。
• 标记法：实现简单，但修改链表节点数据可能不合适。
• 哈希表法：容易理解和实现，但空间复杂度较高。

选择具体方法时，可以根据项目需求和资源限制进行选择。

希望本文对你在C语言中判断链表是否有环有所帮助。