Linked List Cycle I
题目描述
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
判圈算法请看本博客中的Happy Number与Floyd判圈算法
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode fast = head, slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
}
|
Linked List Cycle I
题目描述
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class {
public ListNode detectCycle(ListNode head) {
if(head == null) return head;
ListNode slow = head, fast = head;
boolean isCycle = false;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast ){
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
|
近期评论