给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引进阶你是否可以使用O(1)空间解决此题方法1哈希表第一个重复的节点就是入环的第一个节点如果没有环则走到末尾就退出返回NULLclass Solution { public: ListNode *detectCycle(ListNode *head) { if(!head||!head-next) return NULL; ListNode *pMovehead; unordered_setListNode* _set; while(pMove){ auto it_set.find(pMove); if(it!_set.end()) return *it; _set.insert(pMove); pMovepMove-next; } return nullptr; } };方法2快慢指针一开始令快指针 fast 和慢指针 slow 都位于头部然后快指针每次走 2 步慢指针每次走 1 步因此快指针走的步数始终等于快指针的 2 倍。 假设从头到环入口的距离为 a环长度为 b相遇的时候 a 在环内走了 xb 比 a 多走了 n 环n 为正整数那么有• a 走的距离a x• b 走的距离a x nb• 距离关系2(a x) a x nb可以得到 a x nb也就是说慢指针再往前走 a在环内走的总距离就是 nb 即整数圈慢指针就回到了环入口 而 a 是从头到环入口的距离为 a所以我们再新建一个指针 ptrptr 和 slow 每次同时走 1 步当 ptr 走了 a 步到环入口的时候slow 也正好达到环入口而由于速度一样它们只有可能在环入口相遇所以相遇的位置就是环入口位置.class Solution { public: ListNode *detectCycle(ListNode *head) { if(!head||!head-next) return NULL; ListNode *sMovehead-next; ListNode *fMovehead-next-next; //先判断有没有环 while(fMovesMove){ if(fMovesMove) break; sMovesMove-next; if(fMove) fMovefMove-next; if(fMove) fMovefMove-next; } if(!sMove||!fMove) return nullptr; ListNode *beginPoshead; while(beginPossMove){ if(beginPossMove) return sMove; if(beginPos) beginPosbeginPos-next; if(sMove) sMovesMove-next; } return nullptr; } };推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接