Given a linked list, return the node where the cycle begins. If there is no cycle, return null
.
Can you solve it without using extra space?
思路分析:这题比较容易想到的解法是先检查是否有环,然后检查每个node是否在环内,但是是O(N^2)的解法。这题O(N)的解法需要一定的数学推理,参考了这个题解http://fisherlei.blogspot.com/2013/11/leetcode-linked-list-cycle-ii-solution.html,下面的图也来自这个题解
如下图,假设linked list有环,环周长为Y,环以外的长度是X。
现在有两个指针,第一个指针,每走一次走一步,第二个指针每走一次走两步,如果他们走了t次之后相遇在K点
那么 指针一 走的路是 t = X + nY + K ①
指针二 走的路是 2t = X + mY+ K ② m,n为未知数
把等式一代入到等式二中, 有
2X + 2nY + 2K = X + mY + K
=> X+K = (m-2n)Y ③
这就清晰了,X和K的关系是基于Y互补的,也就是X与K的和是Y的整数倍,等于说,两个指针相遇以后,再往下走X步就回到Cycle的起点了。这就可以有O(n)的实现。
AC Code
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode first = head; ListNode second = head; while(first != null && second != null){ first = first.next; second = second.next; if(second != null) { second = second.next; } if(first == second) break; } if(second == null) return null; second = head; while(first != second){ first = first.next; second = second.next; } return first; } }