此题的距离问题:

  1. Cycle size is s.
  2. slow moves: outer + meet, fast moves: outer + N*s + meet.
  3. outer == (s - meet);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            
            if (fast == slow){
                ListNode slow2 = head; 
                while (slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }
}

更贴切并且重复使用node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public 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
5
while (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.