The Linked List Cycle problem is a classic and frequently asked coding interview question. In this extensive article, we will dive into the Linked List Cycle problem listed on LeetCode, understand the problem statement, explore different approaches to solve it, and implement these solutions in Python.
The Linked List Cycle problem is listed as problem number 141 on LeetCode. Here’s the problem statement:
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.
Input: head = [3,2,0,-4], pos = 1
Input: head = [1,2], pos = 0
Input: head = , pos = -1
Understanding the Problem
In this problem, we are given the head of a singly linked list, and we need to determine whether the linked list contains a cycle. A cycle in a linked list occurs if a node’s next pointer points to any node that was visited earlier in the list.
Preliminary Knowledge: Singly Linked List
Before we discuss solutions, let’s understand what a singly linked list is. A singly linked list is made up of nodes where each node has two components – data and a reference to the next node. The last node in a singly linked list points to
null, signifying the end of the list. In the case of a cyclic linked list, the last node points back to one of the previous nodes instead of
Naive Approach: Hash Set
One simple approach is to keep track of all the nodes that have been visited. We can do this by storing a reference to each visited node in a hash set. As we traverse through the linked list, for each node, we check if it already exists in the hash set. If it does, then we have found a cycle, and we return
true. If we reach the end of the list (i.e., a
null reference), then there is no cycle, and we return
class ListNode: def __init__(self, x): self.val = x self.next = None def hasCycle(head): nodes_seen = set() while head: if head in nodes_seen: return True nodes_seen.add(head) head = head.next return False
This approach has a time complexity of O(n) but also a space complexity of O(n) due to the hash set storing references to n nodes in the worst case.
Optimized Approach: Floyd’s Tortoise and Hare
Floyd’s Tortoise and Hare algorithm is an optimized solution for detecting cycles. It uses two pointers, one moving at a slower pace (tortoise) and the other moving at a faster pace (hare). If there is a cycle, the fast pointer (hare) will eventually meet the slow pointer (tortoise) again. If there isn’t a cycle, the fast pointer will eventually reach the end of the list.
class ListNode: def __init__(self, x): self.val = x self.next = None def hasCycle(head): if not head: return False # Initialize two pointers tortoise = head hare = head.next # Move the tortoise one step and the hare two steps while tortoise != hare: if not hare or not hare.next: return False tortoise = tortoise.next hare = hare.next.next # If the loop exits, there must be a cycle return True
This approach has a time complexity of O(n) as well, but the space complexity is O(1) since it does not use any additional data structures based on the input size.
In this article, we delved into the Linked List Cycle problem on LeetCode. We explored two different solutions to solve this problem in Python. The naive approach utilizing a hash set is simple to understand but consumes additional space. Floyd’s Tortoise and Hare algorithm, on the other hand, is an optimized solution that not only has a linear time complexity but also a constant space complexity.
Understanding the fundamentals of linked lists and pointers is essential to solving such problems. Floyd’s Tortoise and Hare algorithm is not just a solution to this specific problem, but an important algorithm that can be utilized in various scenarios when dealing with sequences.
In coding interviews, providing the optimized solution directly is ideal, but discussing the naive approach and gradually reaching the optimized solution showcases good problem-solving skills and a deep understanding of data structures.