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

5

赠楼

1%

赠楼率

165

蒸汽

670

主题

4114

帖子

5788

积分

大道废,有仁义

▘片十字花瓣▘车资存根

发表于 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 不明觉厉

查看全部评分

回复

使用道具 举报

UID: 1305738

7

赠楼

2%

赠楼率

107

蒸汽

58

主题

2181

帖子

814

积分

发表于 2020-10-10 17:27:25 | 显示全部楼层

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

惊觉我课设快截止了,然而连工程还没建
回复 支持 +

使用道具 举报

UID: 439613

2

赠楼

0%

赠楼率

351

蒸汽

38

主题

2749

帖子

1988

积分

发表于 2020-10-10 17:28:25 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 251357

77

赠楼

7%

赠楼率

115

蒸汽

118

主题

1866

帖子

2789

积分

▘遥远极地▘车资存根▘片十字花瓣

发表于 2020-10-10 17:31:23 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 1364191

0

赠楼

0%

赠楼率

121

蒸汽

4

主题

567

帖子

290

积分

发表于 2020-10-10 17:46:15 | 显示全部楼层

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

原来是你!
这就去给大佬点赞
回复 支持 +

使用道具 举报

UID: 211289

18

赠楼

1%

赠楼率

787

蒸汽

28

主题

428

帖子

1586

积分

发表于 2020-10-10 17:50:09 | 显示全部楼层

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

(去提个 issue 吧
[发帖际遇]: lkwq 挂在市场 4 年的闪卡终于卖掉了,获得体力 1 点 幸运榜 / 衰神榜
回复 支持 +

使用道具 举报

UID: 273648

4

赠楼

1%

赠楼率

302

蒸汽

70

主题

3242

帖子

3021

积分

发表于 2020-10-10 17:54:31 | 显示全部楼层

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

虽然看不懂 但是大佬牛逼
[发帖际遇]: h951753456 和 V 社员工 PY 成功退款了不符合资质的游戏,喜加体力 1 点 幸运榜 / 衰神榜
回复 支持 +

使用道具 举报

UID: 201295

0

赠楼

0%

赠楼率

812

蒸汽

10

主题

382

帖子

1207

积分

/// 矩阵终端 #2637643 ///

▘车资存根

发表于 2020-10-10 17:56:46 | 显示全部楼层

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

是算法大佬!虽然没看懂。
[发帖际遇]: Android 因汇率问题与 PayPal 客服小姐姐愉快交谈,获得补偿体力 1 点 幸运榜 / 衰神榜
回复 支持 +

使用道具 举报

UID: 1313569

41

赠楼

158%

赠楼率

219

蒸汽

52

主题

853

帖子

2350

积分

▘车资存根

发表于 2020-10-10 18:03:54 发自移动设备 - 你的掌上 其乐Keylol 社区 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 213219

0

赠楼

0%

赠楼率

7316

蒸汽

623

主题

4266

帖子

1万

积分

▘干渴水滴▘片十字花瓣▘成人学生卡▘车资存根

发表于 2020-10-10 18:05:00 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 429414

0

赠楼

0%

赠楼率

408

蒸汽

46

主题

598

帖子

1033

积分

发表于 2020-10-10 18:07:53 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 379956

0

赠楼

0%

赠楼率

1048

蒸汽

97

主题

744

帖子

1725

积分

发表于 2020-10-10 18:08:34 | 显示全部楼层

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

我觉得这是利用漏洞,简答题要扣分!
回复 支持 +

使用道具 举报

UID: 193463

9

赠楼

2%

赠楼率

643

蒸汽

193

主题

1万

帖子

1万

积分

四月是你的谎言

▘车资存根▘成人学生卡▘片十字花瓣

发表于 2020-10-10 18:27:13 | 显示全部楼层

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

说到邪道
我就想起来了这个
image.png
社区攻略看到的
当时我就直接傻了

-- 7 Billion Humans (2231) --
-- 10: 疏散演戲 --

step w
step w
a:
step w
if n == datacube and
s == datacube and
sw == hole and
w != hole:
        step w
        step sw
        jump b
endif
if c == datacube and
w == hole and
sw != hole and
sw != wall:
        step sw
        step sw
        jump c
endif
if w == hole and
nw != hole:
        step nw
        step sw
        jump d
endif
if w == hole and
s == wall and
nw == hole:
        step n
        step nw
        step sw
        jump e
else:
        jump a
endif
d:
b:
e:
c:
step s
step sw
step w
step w
step w
step nw
step n
step n
step n
step n
step nw
回复 支持 +1

使用道具 举报

UID: 203050

4

赠楼

0%

赠楼率

140

蒸汽

13

主题

601

帖子

1081

积分

发表于 2020-10-10 18:40:46 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 789130

0

赠楼

0%

赠楼率

911

蒸汽

28

主题

1022

帖子

1613

积分

发表于 2020-10-10 18:43:49 | 显示全部楼层

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


非连续物理地址的堆分配/给你参数之前来了个GC 是不是就无了
回复 支持 +

使用道具 举报

UID: 1315948

6

赠楼

7%

赠楼率

54

蒸汽

17

主题

2397

帖子

968

积分

发表于 2020-10-10 18:48:20 发自移动设备 - 你的掌上 其乐Keylol 社区 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 388819

152

赠楼

15%

赠楼率

1190

蒸汽

207

主题

2430

帖子

2944

积分

▘片十字花瓣

发表于 2020-10-10 18:59:31 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 278164

0

赠楼

0%

赠楼率

149

蒸汽

21

主题

614

帖子

1732

积分

发表于 2020-10-10 19:28:23 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 576873

0

赠楼

0%

赠楼率

70

蒸汽

4

主题

113

帖子

822

积分

发表于 2020-10-10 19:44:15 发自移动设备 - 你的掌上 其乐Keylol 社区 | 显示全部楼层

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

过于邪道,主要还是图一乐
回复 支持 +

使用道具 举报

UID: 467724

2

赠楼

15%

赠楼率

306

蒸汽

155

主题

7146

帖子

3265

积分

▘车资存根

发表于 2020-10-10 20:06:46 | 显示全部楼层
回复 支持 +

使用道具 举报

UID: 708546

17

赠楼

4%

赠楼率

158

蒸汽

146

主题

5963

帖子

3280

积分

▘车资存根

发表于 2020-10-10 20:07:59 | 显示全部楼层

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

过于牛逼,
[发帖际遇]: lerror 在创意工坊发布的 Mod 受到 G 胖青睐,入选不朽饰品,获得体力 1 点 幸运榜 / 衰神榜
回复 支持 +

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

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

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

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