Similar Problems

Valid Phone Numbers

The Linked List Cycle problem on LeetCode is a classic problem that involves identifying whether a linked list has a cycle or not. In this problem, you are given a linked list and are to determine whether it has a cycle or not.

A linked list consists of a series of nodes that are connected to each other. Each node contains a value and a reference to the next node in the list. If the last node in the list has a reference to null, then the linked list is considered to be terminated. However, if any node in the list references an earlier node, then the linked list contains a cycle.

To solve this problem, we need to use the Floyd’s cycle-finding algorithm, also known as the “turtle and hare” algorithm. This algorithm involves traversing the linked list with two pointers, one moving faster than the other. If the linked list contains a cycle, then the faster pointer will eventually catch up to the slower pointer, indicating that a cycle has been found.

Here’s the detailed solution:

1. We start by initializing two pointers, slow and fast, to point to the head of the linked list.
2. We then iterate through the linked list. During each iteration, the slow pointer moves one step forward while the fast pointer moves two steps forward.
3. We check at each step whether the fast pointer has reached the end of the list or not. If it has, then the linked list does not contain a cycle. Otherwise, we continue iterating through the list.
4. If the fast pointer catches up to the slow pointer, then a cycle has been found, and we return true. Otherwise, we return false.

Here’s the Python code that implements this approach:

“`
class Solution:
def hasCycle(self, head: ListNode) -> bool:
return False

``````    slow = head

while slow != fast:
if not fast or not fast.next:
return False

slow = slow.next
fast = fast.next.next

return True
``````

“`

In the code above, we first check whether the head of the linked list is None. If it is, then we know for sure that the linked list does not contain a cycle (since there are no nodes to iterate through).

We then initialize the slow and fast pointers to point to the head of the linked list and its next node, respectively. We then iterate through the linked list using a while loop. During each iteration, we check whether the fast pointer has reached the end of the list (i.e., it is pointing to None), in which case we know for sure that the list does not contain a cycle. Otherwise, we move the slow pointer one step forward and the fast pointer two steps forward.

Finally, if the fast pointer ever catches up to the slow pointer, then we know that a cycle has been found, and we return True. Otherwise, we return False.

This solution has a time complexity of O(n), where n is the number of nodes in the linked list. It also has a space complexity of O(1), since we are only using two pointers to traverse the linked list.

Step by Step Implementation For Linked List Cycle

```/**
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
// if head is null, there is no cycle
return false;
}

// if head.next is null, there is no cycle
return false;
}

// create two pointers, slow and fast
// slow moves one node at a time
// fast moves two nodes at a time

// while fast is not null and fast.next is not null
// keep iterating
while (fast != null && fast.next != null) {
// if slow == fast, there is a cycle
if (slow == fast) {
return true;
}
// move slow one node
slow = slow.next;
// move fast two nodes
fast = fast.next.next;
}

// if we reach here, that means there is no cycle
return false;
}
}```
```# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: bool
"""
# check for empty list
return False

# if only one element in list, can't be a cycle
return False

# use Floyd's cycle detection algorithm
# two pointers, one moves one node at a time,
# the other moves two nodes at a time
# if there is a cycle, the two pointers will eventually meet

while slow != fast:
# check for end of list - no cycle
if not fast or not fast.next:
return False

slow = slow.next
fast = fast.next.next

return True```
```/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/

/**
* @return {boolean}
*/
// if head is null, return false
return false;
}

// define two pointers, slow and fast

// while loop will continue until slow === fast (which means they met in the cycle)
// or fast.next === null (which means there is no cycle)
while (slow !== fast || fast.next !== null) {
// if fast.next is null, that means there is no cycle
if (fast.next === null) {
return false;
}

// move slow pointer one node at a time
slow = slow.next;

// move fast pointer two nodes at a time
fast = fast.next.next;
}

// if the while loop exits, that means there is a cycle
return true;
};```
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (slow != fast) {
if (!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
// if head is null or only has one node, then it can't have a cycle
return false;
}

// use two pointers, slow and fast
// slow moves one node at a time, while fast moves two nodes at a time
// if there is a cycle, slow and fast will eventually meet

while (slow != fast) {
// if fast reaches the end of the list, then there is no cycle
if (fast == null || fast.next == null) {
return false;
}

slow = slow.next;
fast = fast.next.next;
}

return true;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]