leetcode 142 环形链表

淩亂°似流年 2022-09-09 00:23 179阅读 0赞

## 前言 ##

题目：[142. 环形链表 II][142. _ II]

参考答案：[你的疑惑，这里都讲清楚了！142. 环形链表 II - 代码随想录][142. _ II -]

--------------------

## 提交代码 ##

### 直观解 ###

我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。

class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            // if(head==nullptr || head->next==nullptr)
            if(head==nullptr) // 空链表直接返回
                return nullptr;
    
            set<ListNode*> listLop;
            ListNode *it = head;
            while(it != nullptr){
                if(listLop.find(it)==listLop.end())
                    listLop.insert(it);
                else
                    return it;
                it = it->next;
            }
    
            return nullptr;
        }
    };

### 数学解 ###

详细分析过程，见上面参考答案。

首先看懂参考答案中的分析(我没看懂。。)，得到以下结论（但是我可以根据这个结论编程）：

快指针的速度是慢指针的二倍(慢指针的步长为1)，直到第一次相遇。之后，慢指针从头开始遍历，快指针以和慢指针相同的速度(步长均为1)遍历，再次相遇的位置即为环的起始点。

[142. _ II]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[142. _ II -]: https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-jian-hua-gong-shi-jia-2/

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 142. 环形链表 IIJAVA

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开

蔚落/ 2022年12月09日 11:50/ 0 赞/ 86 阅读

相关 LeetCode 142. 环形链表 II

LeetCode 142. 环形链表 II 题目：解题方法：方法1：哈希表法 Java实现方法2：快慢指针

谁借莪１个温暖的怀抱￠/ 2022年11月03日 11:52/ 0 赞/ 187 阅读

相关 leetcode142环形链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

ゝ一世哀愁。/ 2022年10月06日 08:55/ 0 赞/ 168 阅读

相关 leetcode 142 环形链表

前言题目：[142. 环形链表 II][142. _ II] 参考答案：[你的疑惑，这里都讲清楚了！142. 环形链表 II - 代码随想录][142. _ II -

淩亂°似流年/ 2022年09月09日 00:23/ 0 赞/ 180 阅读

相关 Leetcode142. 环形链表 II

难度：`中等` 题目描述： > 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 > > 为了表示给定链表中的环，我们使用整数 pos 来

- 日理万妓/ 2022年09月08日 11:49/ 0 赞/ 293 阅读

相关 Leetcode 142. 环形链表 II

题目重述给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（

缺乏、安全感/ 2022年09月08日 03:49/ 0 赞/ 179 阅读

相关【LeetCode】142. 环形链表 II

题目链接：[https://leetcode-cn.com/problems/linked-list-cycle-ii/description/][https_leetcode

以你之姓@/ 2022年05月13日 14:26/ 0 赞/ 216 阅读

相关【leetcode】142. 环形链表 II

题目描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。示例： > 有环示例： > ![20190226214956725.pn

叁歲伎倆/ 2022年03月16日 13:11/ 0 赞/ 213 阅读

相关 leetcode-142-环形链表②

题目描述： ![1509441-20190717102314870-1677721290.png][] ![1509441-20190717102353296-233

蔚落/ 2021年11月29日 23:48/ 0 赞/ 264 阅读

相关 leetcode：142. 环形链表 II（环形链表找头）

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 `null`。为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从

本是古典何须时尚/ 2021年09月28日 14:52/ 0 赞/ 409 阅读