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

﹏ヽ暗。殇╰゛Y 2022-08-04 00:50 209阅读 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 条评论，209人围观）

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

相关阅读

相关 leetcode 142. Linked List Cycle II

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

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

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

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

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

相关 LeetCode--142. Linked List Cycle II

Problem: > Given a linked list, return the node where the cycle begins. If there is no

蔚落/ 2022年08月21日 00:06/ 0 赞/ 21 阅读

相关 Leetcode: Linked List Cycle II

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

àì夳堔傛蜴生んèń/ 2022年08月07日 11:57/ 0 赞/ 11 阅读

相关 Linked List Cycle II--LeetCode

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

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

相关【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 赞/ 142 阅读

相关【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 赞/ 210 阅读

相关 LeetCode142—Linked List Cycle II

原题 [原题链接][Link 1] > Given a linked list, return the node where the cycle begins. If

缺乏、安全感/ 2022年07月16日 02:20/ 0 赞/ 115 阅读

相关 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 赞/ 148 阅读

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

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

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