|
5 | 5 | importjava.util.HashSet; |
6 | 6 | importjava.util.Set; |
7 | 7 |
|
8 | | -/** |
9 | | - * 141. Linked List Cycle |
10 | | -
|
11 | | - Given a linked list, determine if it has a cycle in it. |
12 | | - To represent a cycle in the given linked list, we use an integer |
13 | | - pos which represents the position (0-indexed) in the linked list where tail connects to. |
14 | | - If pos is -1, then there is no cycle in the linked list. |
15 | | -
|
16 | | - Example 1: |
17 | | - Input: head = [3,2,0,-4], pos = 1 |
18 | | - Output: true |
19 | | - Explanation: There is a cycle in the linked list, where tail connects to the second node. |
20 | | -
|
21 | | - Example 2: |
22 | | - Input: head = [1,2], pos = 0 |
23 | | - Output: true |
24 | | - Explanation: There is a cycle in the linked list, where tail connects to the first node. |
25 | | -
|
26 | | - Example 3: |
27 | | - Input: head = [1], pos = -1 |
28 | | - Output: false |
29 | | - Explanation: There is no cycle in the linked list. |
30 | | -
|
31 | | - Follow up: |
32 | | - Can you solve it using O(1) (i.e. constant) memory? |
33 | | - */ |
34 | 8 | publicclass_141 { |
35 | 9 |
|
36 | | -publicstaticclassSolution1 { |
37 | | -publicbooleanhasCycle(ListNodehead) { |
38 | | -Set<ListNode>set =newHashSet(); |
39 | | -while (head !=null) { |
40 | | -if (!set.add(head)) { |
41 | | -returntrue; |
42 | | -} |
43 | | -head =head.next; |
44 | | -} |
45 | | -returnfalse; |
46 | | -} |
47 | | -} |
48 | | - |
49 | | -publicstaticclassSolution2 { |
50 | | -publicbooleanhasCycle(ListNodehead) { |
51 | | -ListNodeslow =head; |
52 | | -ListNodefast =head; |
53 | | -while (fast !=null &&fast.next !=null) { |
54 | | -fast =fast.next.next; |
55 | | -slow =slow.next; |
56 | | -if (fast ==slow) { |
57 | | -returntrue; |
58 | | -} |
59 | | -} |
60 | | -returnfalse; |
61 | | -} |
62 | | -} |
| 10 | +publicstaticclassSolution1 { |
| 11 | +publicbooleanhasCycle(ListNodehead) { |
| 12 | +Set<ListNode>set =newHashSet(); |
| 13 | +while (head !=null) { |
| 14 | +if (!set.add(head)) { |
| 15 | +returntrue; |
| 16 | +} |
| 17 | +head =head.next; |
| 18 | +} |
| 19 | +returnfalse; |
| 20 | +} |
| 21 | +} |
| 22 | + |
| 23 | +publicstaticclassSolution2 { |
| 24 | +publicbooleanhasCycle(ListNodehead) { |
| 25 | +ListNodeslow =head; |
| 26 | +ListNodefast =head; |
| 27 | +while (fast !=null &&fast.next !=null) { |
| 28 | +fast =fast.next.next; |
| 29 | +slow =slow.next; |
| 30 | +if (fast ==slow) { |
| 31 | +returntrue; |
| 32 | +} |
| 33 | +} |
| 34 | +returnfalse; |
| 35 | +} |
| 36 | +} |
63 | 37 | } |