此题的距离问题:
- Cycle size is
s
. slow
moves:outer + meet
,fast
moves:outer + N*s + meet
.outer == (s - meet)
;
1 | public class Solution { |
更贴切并且重复使用node:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public ListNode detectCycle(ListNode head) {
ListNode car = head, bike = head;
while (car != null && car.next != null) {
car = car.next.next;
bike = bike.next;
if (car == bike) {
bike = head;
while (bike != car) {
car = car.next;
bike = bike.next;
}
return bike;
}
}
return null;
}
另外,很重要的一点:1
2
3
4
5while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
...
为什么while
中的条件是fast != null && fast.next != null
, 而不是fast.next!=null && fast.next.next !=null
, 即使循环体中是fast = fast.next.next; slow = slow.next
?
因为当前node的node.next
可以是null
,但是node.next
如果是null
, 那么node.next.next
就没有任何意义了。所以往下走一个和走两个next条件是当前node和node的next不是null
.