This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 141. This is a Leet code problem named Linked List Cycle. We will solve it using python and it is the best space and time-optimized solution.
Question of Linked List Cycle
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.
Example
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).
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.
Example 3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
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 to solve Cyclic Linked List
We use two pointers to traverse a linked list. One pointer(slow) should be moved by one, while another pointer(fast) should be moved by two. There is a loop if these points intersect at the same node. A linked list does not have a loop if the pointers do not meet.
Algorithm
This method performs the following steps for a given input array:
Check base condition if the linked list does not exist return false.
slow pointer initialized to head
fast pointer initialized to next of head.
Repeat steps 5 to 8 until we did not find None.
return true if fast equals slow
check if next to next of fast is not None. If not then do step 7.
Assign slow=slow.next fast=fast.next.next
if both above conditions are false then return false.
At end return False
Python Code for Cyclic Linked List
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
#base condition if linked list does not exist
if(not head):
return False
#slow pointer initialized to head
slow=head
#fast pointer initialized to next of head
fast=head.next
#run while loop untill we didnt find None
while(slow.next!=None and fast.next!= None):
#return true if fast equals slow
if(fast==slow):
return True
#check if next to next of fast is not None
elif(fast.next.next!=None):
slow=slow.next
fast=fast.next.next
#if both above conditions are false then return false
else:
return False
return False
