链表19---循环链表，找到链表循环的起始位置

灰太狼 2022-05-25 08:35 132阅读 0赞

1、题目：

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?

2、解答： 先用两个指针，一个走一步，一个走两步，它们若相遇一定在链表的循环中，然后另外一个指针从头开始走，slow指针也一步一步的走，若它们相遇，便是起始位置

3、C++代码

class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            
            if(head == NULL|| head->next == NULL)
                 return NULL;
            
            ListNode *slow = head,*fast = head,*entry = head;
            
            while(fast->next && fast->next->next){
                slow = slow->next;
                fast = fast->next->next;
                if(slow == fast){
                    while(slow != entry){
                        slow = slow->next;
                        entry = entry->next;  
                    }
                    return entry;
                }
            }
            return NULL;
        }
    };

python代码

class Solution(object):
        def detectCycle(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            if head == None or head.next == None:
                return None
            
            slow,fast,entry = head,head,head
            
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
                if fast == slow:
                    while entry != slow:
                        entry = entry.next
                        slow = slow.next
                    return entry
            return None

发表评论取消回复

表情：

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

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

相关阅读

相关【链表】单链表、双向循环链表

文章目录前言一：链表(LinkedList) 1.1 链表分类 1.2 介绍 1.3 链表的概念及结构二：

骑猪看日落/ 2024年03月24日 18:19/ 0 赞/ 103 阅读

相关常见的链表——单向链表&双向链表&循环链表

目录目标结构图单向链表的数据结构示意图双向链表的数据结构示意图循环单向链表的数据结构示意图代码实现单向链表双向链表单向循环链表附加题

た入场券/ 2022年09月14日 09:49/ 0 赞/ 342 阅读

相关循环链表

循环链表和单链表没有本质上的差别。唯一不同的链表的最后不再是空的了，而是指向了first头指针。只有这样我们才会实现链表的循环功能，那么问题来了，我们在下面的函数功能中

╰+哭是因爲堅強的太久メ/ 2022年08月13日 13:52/ 0 赞/ 180 阅读

相关循环链表

一、解析将单链表中终端结点的指针端由空指针改为指向头结点，就使整个链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表（circular linked list

男娘i/ 2022年06月18日 09:15/ 0 赞/ 241 阅读

相关循环链表

/循环链表/ include<stdio.h> typedef struct node { int data;

男娘i/ 2022年06月13日 03:41/ 0 赞/ 174 阅读

相关链表19---循环链表，找到链表循环的起始位置

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

灰太狼/ 2022年05月25日 08:35/ 0 赞/ 133 阅读

相关循环链表

循环链表循环链表的原理：最后一个节点的next指向头节点，而不是NULL ![在这里插入图片描述][20181114202301997.png] -

迈不过友情╰/ 2022年04月17日 02:42/ 0 赞/ 197 阅读

相关循环链表

好久没有接触数据结构和算法了，但是这些在面试中还是需要的所以打算重新复习下今天打算用js来实现循环链表，看下别人怎么实现，发现很少使用js实现的，而且实现有点问题在对head

忘是亡心i/ 2022年01月20日 05:15/ 0 赞/ 364 阅读

相关循环链表/双向链表

Java实现循环链表 / @auther: 巨未 @DATE: 2019/1/4 0004 20:12 @Descriptio

深藏阁楼爱情的钟/ 2021年09月23日 07:02/ 0 赞/ 425 阅读

相关循环链表

循环链表的定义和结构在单链表中，使其最后一个结点的指针又指回到第一个结点，这样的线性链表叫做循环链表。 ![Center][] 判断表尾的条件：p→next==L 判

Bertha 。/ 2021年09月10日 23:06/ 0 赞/ 374 阅读