C语言 推理证明带环链表详细过程

背景

链表是一种常见的数据结构。通常，链表节点包括两个部分：数据域和指针域。指针域指向下一个节点的地址，这样就可以将链表的节点串联起来。带环链表是一种特殊的链表，最后一个节点指向链表中第一个节点，形成一个环。

问题

如果一个链表是带环链表，如何判断链表中是否存在环？

分析

假设链表的节点数是N，我们可以定义两个指针，一个指针每次移动一个节点，另一个指针每次移动两个节点。如果链表中不存在环，那么两个指针不可能相遇；如果链表中存在环，那么两个指针肯定会相遇，因为快指针一定会追上慢指针。

使用p1、p2两个指针扫描链表，p1每次移动一个节点，p2每次移动两个节点。如果链表中存在环，那么p1和p2一定会相遇。假设p1和p2在i节点相遇，此时p1移动了m个节点，那么p2移动了2m个节点。假设环的长度是L个节点，那么p2比p1多移动了n次环的长度，即2m = m + nL，也就是m = nL，表示从i节点到相遇节点的距离刚好是n个环长度。

维护两个指针的过程可以使用while循环进行，不过还需要注意两点：

• 当链表为空或者只有一个节点时，肯定不存在环，可以统一返回false
• 当p2到达链表的结尾时，也肯定不存在环，可以统一返回false

代码

下面是一个使用C语言来实现带环链表判断的示例代码

#include <stdio.h>
#include <stdbool.h>

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

bool hasCycle(ListNode *head) {
    if (head == NULL || head->next == NULL) { // 链表为空或只有一个节点，一定不存在环
        return false;
    }

    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast != NULL && fast->next != NULL) { // 快指针到达链表尾部时停止循环
        if (slow == fast) { // 相遇，证明存在环
            return true;
        }
        slow = slow->next; // 慢指针每次移动一个节点
        fast = fast->next->next; // 快指针每次移动两个节点
    }
    return false; // 快指针到达链表尾部都没有相遇，证明不存在环
}

示例

示例一

输入: head = [3,2,0,4], pos = 1
输出: true
解释: 链表中有一个环，其尾部连接到第二个节点。

示例二

输入: head = [1], pos = -1
输出: false
解释: 链表中没有环