算法推导 image 当hare的移动速度是tortoise的 2 倍， 设起始点到环的入口的距离是T，环的长度是C， 当tortoise第一次走到环的入口entry point时，我们假设这是tortoise与hare之间的在环上的距离是r， 从start point开始出发到tortoise第一次走到环的入口时，hare移动的距离是 T + r + k*C，k >= 0， 又因为，hare移动的速度是tortoise的两倍，且这时tortoise移动的距离是T，所以hare移动的距离是 2T。 得到等式 A T + r + k*C = 2T，k >= 0 简化得到等式 B r + k*C = T，k >= 0 [图片上传失败...(image-1940ba-1559799507418)]...阅读全文
题目描述 给定一个链表，判断链表中是否有环。进阶: 你能否不使用额外空间解决此题？ 解题思路 无环链表，最后一个节点为nil，有环链表可以无限循环next下去 不用额外空间：快慢节点，慢节点一次走一步，快节点一次走两步，当进入环中，每次循环，快节点会离慢节点近一步，快节点最终会追上慢节点 用额外空间： 用map存走过的节点，第一个走过的节点就是环的入口 代码实现 // ListNode Definition for singly-linked list. type ListNode struct { Val int Next *ListNode } func hasCycle(head *ListNode) bool { if head != nil { slow := head fast ...阅读全文
题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 说明：不允许修改给定的链表。 进阶: 你能否不使用额外空间解决此题？ 解题思路 无环链表，最后一个节点为nil，有环链表可以无限循环next下去 不用额外空间：快慢节点，慢节点一次走一步，快节点一次走两步，当进入环中，每次循环，快节点会离慢节点近一步，快节点最终会追上慢节点 用额外空间： 用map存走过的节点，第一个走过的节点就是环的入口 不用额外空间 环形链表 设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示 第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b 因为fast的速度是slow的两倍，所以fast走的距离是...阅读全文
题目描述 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 说明：不允许修改给定的链表。进阶: 你能否不使用额外空间解决此题？ 解题思路 无环链表，最后一个节点为nil，有环链表可以无限循环next下去 不用额外空间：快慢节点，慢节点一次走一步，快节点一次走两步，当进入环中，每次循环，快节点会离慢节点近一步，快节点最终会追上慢节点 用额外空间： 用map存走过的节点，第一个走过的节点就是环的入口 不用额外空间 设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示 第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b 因为fast的速度是slow的两倍，所以fast走的距离是slow的两...阅读全文
题目描述 给定一个链表，判断链表中是否有环。 进阶: 你能否不使用额外空间解决此题？ 解题思路 无环链表，最后一个节点为nil，有环链表可以无限循环next下去 不用额外空间：快慢节点，慢节点一次走一步，快节点一次走两步，当进入环中，每次循环，快节点会离慢节点近一步，快节点最终会追上慢节点 用额外空间： 用map存走过的节点，第一个走过的节点就是环的入口 代码实现 // ListNode Definition for singly-linked list. type ListNode struct { Val int Next *ListNode } func hasCycle(head *ListNode) bool { if head != nil { slow := head fast...阅读全文
