Click here to see the problem details. Read the description first.
We will be given a Linked List. We have to determine there is any cycle or not in the linked list. It is an easy problem. See the problem details for the visual representation of the cycle in a linked list.
Coding Part
Generally, in a singly linked list, we start traversing from the head node and ended up in the last node. Where the last node points to the null as the next node reference. If there is a cycle in a singly linked list, it will never reach to end of the list. Instead of that, it will fall into an infinite loop. No node will point to the null as the next node’s reference. See the visual example from the problem details.
To solve this problem, we will use two pointer technique. We will name those pointers slow and fast. We will also use a loop until the list traverse to the end. On the other hand, If there is a cycle in the list, at a point, we will figure out.
In each iteration, the slow pointer goes one step ahead, and the fast pointer goes two steps. If there is a cycle in the list, the fast pointer will catch the slow pointer at some point. Then we can say there is a cycle in the list.
Let’s see the solution in Python below.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseI hope you got the idea. Try to understand the solution with a simple example first.
Happy Learning 🙂
Happy Coding 🙂
