【LeetCode刷题指南】--环形链表，环形链表II(附结论证明过程)

草莓熊Lotso

发布于 2025-10-29 12:07:47

1070

文章被收录于专栏：C++/LinuxC++/Linux

🔥个人主页：@草莓熊Lotso 🎬作者简介：C++研发方向学习者 📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》 ⭐️人生格言：生活是默默的坚持，毅力是永久的享受。

前言：在这篇博客中，博主会为大家分享两个经典的题目，都会用到快慢指针以及相关结论。这些结论会有相关的证明过程，大家一定要注意看一下。

1.环形链表

题目链接：141. 环形链表 - 力扣（LeetCode）

题目描述：

题目示例：

思路： 快慢指针，慢指针每次走一步，快指针每次走两步，如果slow和fast指向同一个节点，说明链表带环

解题过程：

1.创建快慢指针，循环条件的话分奇数和偶数讨论，这里就不详细说了

2.如果快慢指针可以相遇，则返回true

3.如果快慢指针循环结束后还没有相遇，则返回false

具体过程图示如下：

复杂度：

时间复杂度: O(n)
空间复杂度: O(1)

代码演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode*slow=head;
    ListNode*fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        return true;
    }
    return false;
}

结论：快慢指针，慢指针每次走一步，快指针每次走两步，两个链表从起始位置开始，如果链表带环则一定会在环中相遇，否则快指针先走到链表末尾

证明过程如下图：

提示： 虽然已经证明了快指针不论走多少步都可以满足在带环链表中相遇，但是在编写代码的时候会有额外的步骤引入，涉及到快慢指针的算法题中通常习惯使用慢指针走一步快指针走两步的方式。

我们就来看看如果快指针走3步的代码吧

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {
    ListNode *slow, *fast;
    slow = fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        int n = 3; // fast每次⾛三步
        while (n--) {
            if (fast->next)
                fast = fast->next;
            else
                return false;
        }
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

2.环形链表II

题目链接：142. 环形链表 II - 力扣（LeetCode）

题目描述：

题目示例：

思路： 快慢指针在环理一定会相遇，相遇点到入环节点距离等于头节点到入环节点距离，一个从头节点出发，一个从相遇点除法最后一定会在入环节点相遇

解题过程：

1.定义快慢指针，判断能不能相遇

2.如果可以相遇，成环，继续判断，根据结论利用pcur！=slow遍历，直到它们相遇就返回pcur，这样就找到了入环节点

3.如果不能相遇，环都成不了，直接返回NULL

具体过程图示如下：

复杂度：

时间复杂度: O(n)
空间复杂度: O(1)

代码演示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode*slow=head;
    ListNode*fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(slow==fast)
        {
            ListNode*pcur=head;
            while(pcur!=slow)
            {
                pcur=pcur->next;
                slow=slow->next;
            }
            return pcur;
        }
    }
    return NULL;
}