题目要求： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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模板。
今天这道题是每日一题，我的邪道答案点赞数终于超过了正经答案了，哈哈哈哈哈。 目前191赞 已经超过了快慢指针的186赞
| 
发表于 2020-10-10 17:16:40
变色卡
千斤顶
是算法大佬！
