【leetcode每日一题】NO142.Linked List Cycle II

﹏ヽ暗。殇╰゛Y 2022-08-04 00:50 190阅读 0赞

题目：Given a linked list, return the node where the cycle begins. If there is no cycle, return null

解析：根据141题的思路，声明一个慢指针和一个快指针，若存在环，则肯定相遇。借用一篇博客里的图，讲解一下如何求环开始节点。

如下图所示：快慢指针相遇时，快指针走的距离为：f=x+y+z+y；慢指针走的距离为s=x+y；而f=2s；据此我们可以得到x=z。所以在相遇后，我们可以让慢指针指向头结点，当两个指针再次相遇的位置，即为环开始的节点。

![Center][]

代码：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            ListNode *fast,*slow;
            fast=head;
            slow=head;
            while(fast!=NULL&&fast->next!=NULL)
            {
                fast=fast->next->next;
                slow=slow->next;
                if(fast==slow)
                    break;
            }
            if(fast==NULL||fast->next==NULL)
                return NULL;
            slow=head;
            while(slow!=fast)
            {
                slow=slow->next;
                fast=fast->next;
            }
            return slow;
        }
    };

[Center]: /images/20220731/154e716e786d4acc985cd2d789328c8e.png

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 142. Linked List Cycle II

目录一、问题描述二、代码实现 1、使用Set 2、双指针法（快慢指针） -------------------- [https://leetcode.co

深藏阁楼爱情的钟/ 2023年07月13日 03:23/ 0 赞/ 10 阅读

相关 LeetCode - Medium - 142. Linked List Cycle II

Topic Linked List Two Pointers Math Description [https://leetcode.com/pr

不念不忘少年蓝@/ 2022年12月29日 02:07/ 0 赞/ 152 阅读

相关 Linked List Cycle II--LeetCode

这道题是Linked List Cycle的扩展，就是在确定是否有cycle之后还要返回cycle的起始点的位置。从Linked List Cycle中用的方法我们可以得知a=

不念不忘少年蓝@/ 2022年08月07日 10:57/ 0 赞/ 8 阅读

相关【leetcode每日一题】NO92.Reverse Linked List II

题目：Reverse a linked list from position m to n. Do it in-place and in one-pass. For

清疚/ 2022年08月04日 04:14/ 0 赞/ 127 阅读

相关【leetcode每日一题】NO142.Linked List Cycle II

题目：Given a linked list, return the node where the cycle begins. If there is no cycle, re

﹏ヽ暗。殇╰゛Y/ 2022年08月04日 00:50/ 0 赞/ 191 阅读

相关【leetcode每日一题】NO206.Reverse Linked List

题目：Reverse a singly linked list.即单链表反序。解析：链表反序是很常见的题目，不过多解释了，直接上代码。 / Defin

朴灿烈づ我的快乐病毒、/ 2022年08月03日 23:55/ 0 赞/ 162 阅读

相关 [Leetcode][python]Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II

Linked List Cycle 题目大意判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？解题思路哈希表快慢指针代码

雨点打透心脏的1/2处/ 2022年06月04日 01:59/ 0 赞/ 179 阅读

相关 142. Linked List Cycle II - Leetcode

142. Linked List Cycle II Problems: Given a linked list, return the node where the

川长思鸟来/ 2022年05月23日 13:10/ 0 赞/ 123 阅读

相关 LeetCode 142.Linked List Cycle II (环形链表 II) 详解

题目描述：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 `null`。说明：不允许修改给定的链表。进阶：你是否可以不用额外空间解决此题？

约定不等于承诺〃/ 2022年05月08日 13:22/ 0 赞/ 158 阅读

相关 LeetCode：142. Linked List Cycle II（找出链表中的环）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

分手后的思念是犯贱/ 2022年04月05日 09:10/ 0 赞/ 158 阅读