Introducation
This article explores the challenge of detecting cycles in linked lists, a simple but fundamental concept in computer science and a frequent problem in software development interviews. Through my experience, I’ve encountered this problem firsthand in a technical interview, underscoring its practical importance. The article aims to provide clear and insightful solutions to help understand and solve this problem effectively.
To facilitate a comprehensive understanding, we will explore practical solutions accompanied by illustrative examples in Java and Python,
The Problem
The issue is determining whether a cycle exists within a linked list. In essence, a linked list is a linear data structure where each node not only holds a value but also a pointer directing to the subsequent node. Under ideal circumstances, the last node of a linked list should point to null, signaling the list’s conclusion. However, complications arise when a node links back to an earlier one in the list, forming a cycle. This scenario can lead to significant problems, such as endless loops.
An illustrative diagram below demonstrates a linked list entangled in such a cycle.
Set to record each visited node. As we navigate through the list, we add every node we encounter into the Set. Encountering a node that has already been added to the Set signals that a cycle exists. Using a Set to Store Visited Nodes: Java and Python Code Examples
import java.util.HashSet;
import java.util.Set;
public class LinkedListCycle {
public static boolean containsCycle(Node head) {
Set<Node> visited = new HashSet<>();
Node currentNode = head;
while (currentNode != null) {
if (visited.contains(currentNode)) {
return true;
}
visited.add(currentNode);
currentNode = currentNode.next;
}
return false;
}
public static void main(String[] args) {
Node n8 = new Node(8);
Node n10 = new Node(10);
Node n5 = new Node(5);
Node n1 = new Node(1);
n8.next = n10;
n10.next = n5;
n5.next = n1;
n1.next = n10;
System.out.println(containsCycle(n8));
}
}
class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedListCycle:
@staticmethod
def containsCycle(head):
visited = set()
current_node = head
while current_node:
if current_node in visited:
return True
visited.add(current_node)
current_node = current_node.next
return False
# Example
if __name__ == "__main__":
n8 = Node(8)
n10 = Node(10)
n5 = Node(5)
n1 = Node(1)
n8.next = n10
n10.next = n5
n5.next = n1
n1.next = None # no cycle
print("Contains cycle? ", LinkedListCycle.containsCycle(n8)) # should return False
# Setting a cycle
n1.next = n10
print("Contains cycle? ", LinkedListCycle.containsCycle(n8)) # should return TrueUsing a Set to Store Visited Nodes: Complexity Analysis
Time Complexity Analysis
- Set Operations: Insertion and search in a
Settypically have an average time complexity of O(1), thanks to hashing which facilitates quick access operations. - Traversal of the Linked List: Each node in the list is visited only once, with a search and possibly an insertion in the
Setbeing performed at each node. - Overall Time: For a linked list with ‘N’ nodes, the total time complexity is O(n), as each node is accessed once, and for each node, the operations on the Set are executed in constant time.
Space Complexity Analysis
- Storing Visited Nodes: The proposed solution uses a
Set(in Java) orset(in Python) to track the visited nodes in the linked list. The additional space used is for storing these nodes in the Set. - Total Space Usage: In the worst-case scenario, where there’s no cycle, all nodes will be added to the Set. Hence, the worst-case space complexity is O(n), where ‘n’ is the total number of nodes in the linked list.
Solution 2: The Two-Pointer Technique for Cycle Detection
This method employs two pointers moving at different speeds through the list—one faster and one slower. If there’s a cycle in the list, the faster pointer will eventually catch up to the slower one, indicating the presence of a cycle
The Two-Pointer Technique for Cycle Detection: Java and Python Code Examples
public class LinkedListCycle {
public static boolean containsCycle(Node head) {
if (head == null) return false;
Node slow = head;
Node faster = head.next;
while (faster != null && faster.next != null) {
if (faster == slow) {
return true; // Cycle detected
}
slow = slow.next; // Move one step
faster = faster.next.next; // Move two steps
}
return false; //No cycle detected
}
public static void main(String[] args) {
Node n8 = new Node(8);
Node n10 = new Node(10);
Node n5 = new Node(5);
Node n1 = new Node(1);
n8.next = n10;
n10.next = n5;
n5.next = n1;
n1.next = n10;
System.out.println(containsCycle(n8));
}
}
class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
this.next = null;
}
}
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedListCycle:
@staticmethod
def containsCycle(head):
visited = set()
current_node = head
while current_node:
if current_node in visited:
return True #Cycle detected
visited.add(current_node)
current_node = current_node.next
return False #No cycle detected
# Example
if __name__ == "__main__":
n8 = Node(8)
n10 = Node(10)
n5 = Node(5)
n1 = Node(1)
n8.next = n10
n10.next = n5
n5.next = n1
n1.next = None # no cycle
print("Contains cycle? ", LinkedListCycle.containsCycle(n8)) # should return False
# Setting a cycle
n1.next = n10
print("Contains cycle? ", LinkedListCycle.containsCycle(n8)) # should return TrueThe Two-Pointer Technique for Cycle Detection: Complexity Analysis
Time Complexity Analysis
In this solution, two pointers moving at different speeds are used in the linked list—one ‘slow’ and one ‘fast’.
- Scenario without a cycle: In this scenario the fast pointer will reach the end of the list. Since the fast pointer moves two steps at a time and the slow one step, the maximum iterations are less than 2N, where N is the number of nodes.
- Cyclic scenario: In a cyclic scenario, the fast pointer will eventually catch up to the slow pointer inside the cycle. The iterations depend on the cycle’s size and start position but are significantly fewer than 2N.
Thus, the general time complexity is O(n), where n is the number of nodes.
Space Complexity Analysis
The main advantage of this two-pointer solution is its minimal additional space requirement, regardless of the linked list size. It uses only two extra pointers, independent of the number of nodes in the list. Consequently, the total space complexity is O(1), indicating that the space used does not increase with the size of the linked list.
Conclusion
In this article, we’ve delved into two effective methods for detecting cycles in linked lists—a frequent challenge in technical interviews for top tech companies. The Set-based solution offers simplicity and time efficiency, while the two-pointer method excels in space efficiency. Both have their unique strengths, allowing choice based on specific problem needs and constraints.
👨💻 Don’t forget to share your experiences or questions in the comments! And if you found this helpful, share it with friends gearing up for interviews! 👩💻🚀
References
Cracking the Coding Interview: This book is a renowned best-seller and a personal favorite – an essential book for preparing for technical interviews!
Designing Data-Intensive Applications: ‘ is a go-to reference for creating scalable, robust, and high-performance applications!
For those interested in a Portuguese version of this article, please click here to access it.
Pingback: Adding Numbers Using Linked Lists: Java & Python Solutions - Art of Coding