A
A
Algorithm Practice
Search…
A
A
Algorithm Practice
Introduction
Lintcode
Leetcode
Math
Tree
Graph
Two Pointers
Linked List
2 Add Two Numbers
21 Merge Two Sorted Lists
23 Merge k Sorted Lists
61 Rotate List
82 Remove Duplicates from Sorted List II
83 Remove Duplicates from Sorted List
86 Partition List
92 Reverse Linked List II
109 Convert Sorted List to Binary Search Tree
141 Linked List Cycle
142 Linked List Cycle II
203 Remove Linked List Elements
206 Reverse Linked List
234 Palindrome Linked List
237 Delete Node in a Linked List
328 Odd Even Linked List
369 Plus One Linked List
379 Design Phone Directory
445 Add Two Numbers II
725 Split Linked List in Parts
817 Linked List Components
148 Sort List
Topological Sort
Hash Table
Trie
Sort
Binary Search
Heap
Breadth First Search
Stack
Backtracking
Dynamic Programming
Union Find
Scan Line
String
Reservoir Sampling
Recursion
Google
Powered By GitBook
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)
Previous
109 Convert Sorted List to Binary Search Tree
Next
142 Linked List Cycle II
Last modified 2yr ago
Copy link
Contents
141. Linked List Cycle
1. Question
2. Implementation
3. Time & Space Complexity