|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.classes.ListNode; |
4 | 4 |
|
| 5 | +importjava.util.HashSet; |
| 6 | +importjava.util.Set; |
| 7 | + |
5 | 8 | publicclass_142 { |
6 | 9 |
|
7 | 10 | publicstaticclassSolution1 { |
| 11 | +publicListNodedetectCycle(ListNodehead) { |
| 12 | +Set<ListNode>seen =newHashSet<>(); |
| 13 | +while (head !=null) { |
| 14 | +if (!seen.add(head)) { |
| 15 | +returnhead; |
| 16 | + } |
| 17 | +head =head.next; |
| 18 | + } |
| 19 | +returnnull; |
| 20 | + } |
| 21 | + } |
| 22 | + |
| 23 | +publicstaticclassSolution2 { |
| 24 | +/** |
| 25 | + * This comment explains it really well for this solution: |
| 26 | + * https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation./44281 |
| 27 | + * |
| 28 | + * When fast and slow meet for the first time at point P, fast travelled (a + b + c + b) |
| 29 | + * and slow travelled (a + b), and we know fast travels twice fast as slow, so we have: |
| 30 | + * a + b + c + b = 2*(a + b), this gives us a == c; |
| 31 | + * so at point P, we start a new slow2 pointer from the head, when both slow and slow2 travelled distance a, they must meet |
| 32 | + * at cycle entrance point Q. |
| 33 | + */ |
8 | 34 | publicListNodedetectCycle(ListNodehead) { |
9 | 35 | ListNodeslow =head; |
10 | 36 | ListNodefast =head; |
|