这波啊，这波是邪道算法的胜利

sinstar · 发表于 2020-10-10 17:16:40

题目链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/

题目要求：

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

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

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

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

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

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

1. 一般内存都在在堆上申请的，而堆的地址空间是从低到高的；

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

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

1. 等于的情况是链表只有一个节点，并和自己组成了一个环。

2. 如果链表中不存在环，则最后一个节点的下一个节点是nullptr，也就是0，而0小于等于任何地址。

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

那么，成了！详细代码如下。

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
while(head) {
if(!less<ListNode *>()(head, head->next)) {
return head->next;
}
head = head->next;
}
return nullptr;
}
};

复制代码

注1：C＋＋中并不能直接使用操作符<、>对指针（地址）进行比较，所以采用less模板。

注2：https://www.acfun.cn/a/ac4989648

今天这道题是每日一题，我的邪道答案点赞数终于超过了正经答案了，哈哈哈哈哈。

目前191赞

已经超过了快慢指针的186赞

评分

▘片十字花瓣

▘车资存根

积分封禁

预备会员

管理员

超级版主

版主

禁言会员

封禁帐户

封禁网段

游客

待验证用户

论坛贵宾

实习版主

群组维护

初阶会员

QQ游客

绿光作者

平台开发者

浪人

认证发行商

研发支持

进阶会员

高阶会员

精锐会员

支柱会员

核心会员

旗舰会员

毕业会员