> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/linked-list-cycle.md).
# 141. Linked List Cycle
### Description
Given `head`, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to. **Note that `pos` is not passed as a parameter**.
Return `true` *if there is a cycle in the linked list*. Otherwise, return `false`.
### Constraints
* The number of the nodes in the list is in the range `[0, 104]`.
* `-105 <= Node.val <= 105`
* `pos` is `-1` or a **valid index** in the linked-list.
### Approach
### Links
* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/linked-list-cycle/)
* ProgramCreek
* YouTube
### **Examples**
{% tabs %}
{% tab title="Example 1" %}
**Input:** head = \[3, 2, 0, -4], pos = 1
**Output:** true
**Explanation:** There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
{% endtab %}
{% tab title="Example 2" %}
**Input:** head = \[1, 2], pos = 0
**Output:** true
**Explanation:** There is a cycle in the linked list, where the tail connects to the 0th node.
{% endtab %}
{% tab title="Example 3" %}
**Input:** head = \[1], pos = -1
**Output:** false
**Explanation:** There is no cycle in the linked list.
{% endtab %}
{% endtabs %}
### **Solutions**
{% tabs %}
{% tab title="ListNode" %}
```java
// Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
```
{% endtab %}
{% tab title="Solution 1" %}
```java
/**
* Time complexity : O(n). We visit each of the nn elements in the list at
* most once. Adding a node to the hash table costs only O(1)O(1) time.
* Space complexity : O(n). The space depends on the number of elements
* added to the hash table, which contains at most nn elements.
*/
public boolean hasCycle(ListNode head) {
Set nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
```
{% endtab %}
{% tab title="Solution 2" %}
```java
/**
* Time complexity : O(N), If list has no cycle. O(N+K), If list has a cycle.
* Space complexity : O(1). We only use two nodes (slow and fast).
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slowptr = head;
ListNode fastptr = head.next;
while(slowptr != fastptr) {
if(fastptr == null || fastptr.next == null) {
return false;
}
slowptr = slowptr.next;
fastptr = fastptr.next.next;
}
return true;
}
}
```
{% endtab %}
{% endtabs %}
### **Follow up**
* Can you solve it using `O(1)` (i.e. constant) memory?
