回复
20
查看
1182
收藏
8
UID: 249303

5

赠楼

1%

赠楼率

393

蒸汽

742

主题

4345

帖子

6225

积分

大道废,有仁义

▘片十字花瓣▘车资存根

发表于 2020-10-10 17:16:40 | 显示全部楼层 |阅读模式

资料 加好友 聊天 库存 截图 好友 群组 愿望单 评测 信誉+36/-0




题目要求:
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

进阶:你是否可以不用额外空间解决此题?

o_1d51lsi52thktq61v2iccm9eq7.png

一般有两种解题思路,一是利用set来存储链表节点的地址,看哪个重复了,哪个就是入环的第一个节点;二是利用快慢指针,一个快指针,一个慢指针,同时遍历链表看是否存在环,然后再进一步寻找入环的第一个节点。


这里我们不去考虑算法,我们考虑程序自身的特点,我们都知道,

1. 一般内存都在在堆上申请的,而堆的地址空间是从低到高的;
2. 一般我们给链表申请内存空间的时候,一般都是逐个申请并链接,这样链表里的节点的地址也是从低到高的;幸运的是LeetCode的开发者的也是这样想的,(●'◡'●),这一点是关键。

那么,如果链表里面存在环,那么入环第一个节点的地址一定小于或等于最后一个节点的地址。我们只需要返回第一个地址小于或等于前一个节点的节点,即可。

1. 等于的情况是链表只有一个节点,并和自己组成了一个环。
2. 如果链表中不存在环,则最后一个节点的下一个节点是nullptr,也就是0,而0小于等于任何地址。

这样我们的算法只需要遍历一遍链表,并且不使用额外的内存空间,算法复杂度o(n),空间复杂度o(1)。

那么,成了!详细代码如下。

  1. class Solution {
  2. public:
  3.     ListNode *detectCycle(ListNode *head) {
  4.         while(head) {
  5.             if(!less<ListNode *>()(head, head->next)) {
  6.                 return head->next;
  7.             }
  8.             head = head->next;
  9.         }
  10.         return nullptr;
  11.     }
  12. };
复制代码
注1:C++中并不能直接使用操作符<、>对指针(地址)进行比较,所以采用less模板。

今天这道题是每日一题,我的邪道答案点赞数终于超过了正经答案了,哈哈哈哈哈。
目前191赞
image.png
已经超过了快慢指针的186赞
image.png

评分

参与人数 10体力 +17 收起 理由
UID: 369003 Jianrry + 3 给dalao递体力
UID: 458995 sanyaze + 2 原创精华
UID: 217733 DC_LangX + 2 给dalao递体力
UID: 1005837 noob101 + 1 给dalao递体力
UID: 1213836 tuhaoyan + 1 给dalao递体力
UID: 340299 september130018 + 2 给dalao递体力
UID: 251953 元心 + 2 给dalao递体力
UID: 1305738 lites001 + 1 给dalao递体力
UID: 518543 zlm83459 + 1 老哥稳
UID: 562667 yuyym + 2 不明觉厉

查看全部评分

回复

使用道具 举报

历史主题仅可以浏览第一页回复。如觉得帖子有价值,请前往 https://keylol.com/t643476-1-1 恢复。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

欢迎发帖参与讨论 o(*≧▽≦)ツ,请注意
1. 寻求帮助或答案的帖子请发到问题互助版块,悬赏有助于问题解决的速度。发错可能失去在该板块发布主题的权限(了解更多
2. 表达观点可以,也请务必注意语气和用词,以免影响他人浏览。如觉得违规可使用举报功能 交由管理人员处理,请勿引用对方的内容。
3. 开箱晒物交易中心游戏互鉴福利放送版块请注意额外的置顶版规。
4. 除了提问帖和交易帖以外,不确认发在哪个版块的帖子可以先发在谈天说地

  作为民间站点,自 2004 年起为广大中文 Steam 用户提供技术支持与讨论空间。历经十余载风雨,如今已发展为国内最大的正版玩家据点。

列表模式 · · 微博 · Bilibili频道 · Steam 群组 · 贴吧 · QQ群 
Keylol 其乐 ©2004-2021 Chinese Steam User Fan Site.
Designed by Lee in Balestier, Powered by Discuz!
推荐使用 ChromeMicrosoft Edge 来浏览本站
广告投放|文字版|手机版|其乐 Keylol ( 粤ICP备17068105号-2 )
GMT+8, 2021-6-17 10:03, PE: 0.030293s , QE: 17, Redis On.
快速回复 返回顶部 返回列表