转载

[原]LeetCode Linked List Cycle II

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。

[原]LeetCode Linked List Cycle II

现在有两个指针,第一个指针,每走一次走一步,第二个指针每走一次走两步,如果他们走了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;     } }
正文到此结束
Loading...