141 Linked List Cycle

1. Question

Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) {
7
* val = x;
8
* next = null;
9
* }
10
* }
11
*/
12
public class Solution {
13
public boolean hasCycle(ListNode head) {
14
ListNode slow = head, fast = head;
15
16
while (fast != null && fast.next != null) {
17
fast = fast.next.next;
18
slow = slow.next;
19
20
if (fast == slow) {
21
return true;
22
}
23
}
24
return false;
25
}
26
}
Copied!

3. Time & Space Complexity

时间复杂度: O(n), 空间复杂度: O(1)