LeetCode刷题(25)~环形链表

举报
海轰Pro 发表于 2021/08/06 00:29:36 2021/08/06
【摘要】 题目描述 给定一个链表,判断链表中是否有环。 解答 By 海轰 提交代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; *...

题目描述

给定一个链表,判断链表中是否有环。

解答 By 海轰

提交代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public: bool hasCycle(ListNode *head) { if(head==NULL||head->next==NULL) return false; ListNode* slow=head; ListNode* fast=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) return true; } return false; }
};

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

运行结果
在这里插入图片描述
思路
        利用快慢指针!如果存在环,则最后快指针一定可以追上慢指针;若不存在环,则快指针会移动到nullptr。

其他解答

哈希表

 bool hasCycle(ListNode *head) { unordered_map<ListNode*,int> a; while(head) { ++a[head]; if(a[head]>1) return true; head=head->next; } return false; }

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

运行结果
在这里插入图片描述
思路
        利用哈希表存储每一个遍历的节点,如果存在环,则一定有节点遍历了两次及以上,就直接return true即可。

文章来源: haihong.blog.csdn.net,作者:海轰Pro,版权归原作者所有,如需转载,请联系作者。

原文链接:haihong.blog.csdn.net/article/details/107875465

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。