LeetCode刷题（C++）——Linked List Cycle II（Medium）

心已赠人 2022-06-15 00:41 129阅读 0赞

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

Note: Do not modify the linked list.

Follow up:  
Can you solve it without using extra space?

/**
     * 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) {
            if (head == NULL)
    			return NULL;
    		ListNode* fast = head->next;
    		ListNode* slow = head;
    		while (fast != NULL) {
    			if (fast == slow) {
    				break;
    			}
    			slow = slow->next;
    			fast = fast->next;
    			if (fast != NULL)
    				fast = fast->next;
    		}
    		if (fast != NULL) {
    			int count = 1;
    			while (slow->next != fast){
    				++count;             //统计环中结点的个数
    				slow = slow->next;
    			}
    			slow = fast = head;
    			for (int i = 0; i < count;i++)
    				fast = fast->next;
    			while (slow != fast)
    			{
    				fast = fast->next;
    				slow = slow->next;
    			}
    		}
    		return fast;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 Leetcode: Linked List Cycle

题目： Given a linked list, determine if it has a cycle in it. 思路分析：利用快慢指针slow，fast。

妖狐艹你老母/ 2022年08月07日 11:56/ 0 赞/ 27 阅读

相关 Linked List Cycle II--LeetCode

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

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

相关 Linked List Cycle--LeetCode

题目： Given a linked list, determine if it has a cycle in it. Follow up: Can you solv

谁借莪１个温暖的怀抱￠/ 2022年08月07日 10:55/ 0 赞/ 19 阅读

相关 [leetcode] Linked List Cycle

Problem: Given a linked list, determine if it has a cycle in it. Follow up: Can you

朴灿烈づ我的快乐病毒、/ 2022年07月17日 02:37/ 0 赞/ 87 阅读

相关 LeetCode141—Linked List Cycle

原题 [原题链接][Link 1] > Given a linked list, determine if it has a cycle in it. > > Fol

淡淡的烟草味﹌/ 2022年07月16日 00:11/ 0 赞/ 157 阅读

相关 LeetCode刷题（C++）——Linked List Cycle II（Medium）

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

心已赠人/ 2022年06月15日 00:41/ 0 赞/ 130 阅读

相关 LeetCode刷题（C++）——Linked List Cycle（Easy）

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it w

快来打我*/ 2022年06月15日 00:38/ 0 赞/ 137 阅读

相关 LeetCode刷题笔记（链表）：linked-list-cycle-ii

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

骑猪看日落/ 2022年06月01日 00:39/ 0 赞/ 175 阅读

相关 LeetCode刷题笔记（链表）：linked-list-cycle

-------------------- 转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net

亦凉/ 2022年06月01日 00:39/ 0 赞/ 200 阅读

相关【leetcode82】Linked List Cycle

题目描述：判断有序list是不是环要求：时间复杂度o（n）原文描述： Given a linked list, determine if it

た入场券/ 2022年04月11日 06:41/ 0 赞/ 135 阅读