LeetCode141—Linked List Cycle

淡淡的烟草味﹌ 2022-07-16 00:11 264阅读 0赞

## 原题 ##

[原题链接][Link 1]

> Given a linked list, determine if it has a cycle in it.
> 
> Follow up:  
> Can you solve it without using extra space?

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

## 分析1 ##

简单的版本就是用个set记录一下已经访问的节点，如果有环肯定会走回去。

class Solution {
        public:
        bool hasCycle(ListNode *head) {
            ListNode * p = new ListNode(0);
            p->next=head;
            unordered_set<ListNode *>visit;
            bool flag=false;
            while(p&&p->next)
            {
                if(visit.find(p)==visit.end())
                {
                    visit.insert(p);
                    p=p->next;
                }
                else
                {
                    flag=true;
                    break;
                }
            }
            if(flag)
                return true;
            else
                return false;
        }
    
    };

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

## 分析2 ##

考虑题目中提到如果不用额外的空间？  
可以用两个指针，一个一次跳两个，一个一次跳一个，如果有圈的话，总有一天，跳两个的会和跳一格的重合。

class Solution {
    public:
        bool hasCycle(ListNode *head) {
            ListNode *p1 =head;
            ListNode *p2=head;
            while(p2&&p2->next)
            {
                p1=p1->next;
                p2=p2->next->next;
                if(p1==p2)
                    return true;
            }
            return false;
        }
    };

[Link 1]: https://leetcode.com/problems/linked-list-cycle/

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode（Linked List)141. Linked List Cycle

1.问题 iven head, the head of a linked list, determine if the linked list has a cycle i

快来打我*/ 2023年09月24日 17:38/ 0 赞/ 39 阅读

相关 leetcode 141. Linked List Cycle

[https://leetcode.com/problems/linked-list-cycle/][https_leetcode.com_problems_linked-li

喜欢ヅ旅行/ 2023年07月13日 03:19/ 0 赞/ 165 阅读

相关 LeetCode - Easy - 141. Linked List Cycle

Topic Two Pointers Linked List Description [https://leetcode.com/problems/l

雨点打透心脏的1/2处/ 2022年12月29日 00:10/ 0 赞/ 289 阅读

相关 [leetcode]141. Linked List Cycle

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

刺骨的言语ヽ痛彻心扉/ 2022年08月22日 00:08/ 0 赞/ 168 阅读

相关 141. Linked List Cycle

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

冷不防/ 2022年08月21日 00:03/ 0 赞/ 274 阅读

相关 #141 Linked List Cycle

这是一道简单的中级题，本想上道题做完就不做了的，结果看到这个好简单就还是做一下吧~ [\141 Linked List Cycle][141 Linked List Cycl

素颜马尾好姑娘i/ 2022年08月02日 04:59/ 0 赞/ 259 阅读

相关 141. Linked List Cycle

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

怼烎@/ 2022年07月29日 08:50/ 0 赞/ 263 阅读

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

相关 [leetcode]: 141. Linked List Cycle

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

﹏ヽ暗。殇╰゛Y/ 2022年06月15日 09:44/ 0 赞/ 279 阅读

相关（Java）leetcode-141 Linked List Cycle

题目【判断链表是否有环】 Given a linked list, determine if it has a cycle in it. To represent

港控/mmm°/ 2022年02月28日 02:28/ 0 赞/ 332 阅读