[牛客网刷题 Day4] JZ23 链表中环的入口结点

本文主要是介绍[牛客网刷题 Day4] JZ23 链表中环的入口结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

思考：

建立一个list，存储节点，出现重复，就返回。

class Solution:def EntryNodeOfLoop(self, pHead):if pHead is None or pHead.next is None:return Nonemem = []while pHead not in mem:mem.append(pHead)pHead = pHead.nextif pHead is None:return Noneelse:return pHead

答案：

答案用的是set()，占用内存比list少了很多很多；以后记得多用set，它不允许重复

上述答案需要的空间复杂度为$O(n)$，还要一种答案是双指针，空间复杂度为$O(1)$
要解方程呢~

假设环外长度为a，环内长度为b；快指针一次移两格，慢指针一次移一格；

• 快指针走到入口处满足：$fast=a+n\ast b$；
• 快慢指针一定会在环内相遇，此时 $fast-slow=n\ast b$；又因为$fast=2\ast slow$，代入一下，相遇时$slow=n\ast b$
• 相遇后，让fast回到头结点，慢指针继续走，当二者再次相遇时，就是头结点了；$slow=n\ast b+a$，刚好会和快节点在入口相遇呢。

看了好一会儿才看明白，这也太巧妙了吧

class Solution:def EntryNodeOfLoop(self, pHead):# write code hereslow = pHeadfast = pHeadwhile fast !=None and fast.next !=None:fast = fast.next.nextslow = slow.nextif slow == fast:while pHead != slow:pHead =pHead.nextslow = slow.nextreturn slowreturn None

这篇关于[牛客网刷题 Day4] JZ23 链表中环的入口结点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---