There is a formula for his question: t mod n = (k + 2t) mod n
/**
* 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 oneStep = head;
ListNode twoStep = head;
while(twoStep != null && twoStep.next != null ){
oneStep = oneStep.next;
twoStep = twoStep.next.next;
if(oneStep == twoStep){
break;
}
}
if(twoStep == null || twoStep.next == null){
return null;
}else{
oneStep = head;
while(oneStep != twoStep){
oneStep = oneStep.next;
twoStep = twoStep.next;
}
}
return oneStep;
}
}
没有评论:
发表评论