LeetCode141—Linked List Cycle

淡淡的烟草味﹌ 2022-07-16 00:11 113阅读 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 条评论，113人围观）

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

相关阅读

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

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

相关 #141 Linked List Cycle

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

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

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

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

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

相关 141.linked list cycle

/\ 判断输入的链表是否是循环链表思路：利用快慢指针，一个是p = p->next;另外一个是q = q->next；如果两个指针相遇了，则说明是循环链表 \/

男娘i/ 2022年06月10日 14:11/ 0 赞/ 120 阅读

相关 LeetCode 141.Linked List Cycle (环形链表)

题目描述：给定一个链表，判断链表中是否有环。进阶：你能否不使用额外空间解决此题？ AC C++ Solution: 解题思路：使用两个指针，一个指针一次走

港控/mmm°/ 2022年05月08日 13:22/ 0 赞/ 104 阅读

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

相关 141. Linked List Cycle

1. 原始题目 Given a linked list, determine if it has a cycle in it. To represent a cycle

水深无声/ 2021年12月10日 08:49/ 0 赞/ 193 阅读