Linked List Cycle II LeetCode

Key takeaways:
A cycle in a linked list occurs when nodes loop back, allowing repeated visits.
The task is to find the starting node of the cycle, or return null if none exists.
The algorithm uses a set to track visited nodes:
If a node is revisited, it’s the start of the cycle and is returned.
If no cycle is detected, the function returns null.
Time complexity is $O(n)$ —each node is visited once.
Space complexity is $O(n)$ —all nodes are stored in a set if no cycle is found.

In linked list data structures, a cycle occurs when a series of nodes loops back to an earlier node in the list, creating an infinite loop if traversed continuously. Detecting the starting node of a cycle is crucial in real-world applications, such as analyzing computer memory management and network routing loops, where misconfigurations might lead to infinite loops and system crashes. By identifying the start of a cycle, we can prevent unintended consequences and optimize the performance of these systems. In this Answer, we’ll explore an efficient method to detect a cycle’s starting node in a linked list.

Problem statement

Given the head of a linked list, identify and return the node where the cycle originates. If no cycle is present, return null.

Constraints:

$0 \leq$ numbers of nodes $\leq 10^4$
$-10^5 \leq$ node.value $\leq 10^5$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Algorithm

To detect the presence of a cycle in a linked list and identify the node where the cycle begins, we can use a set to keep track of visited nodes. This approach ensures that we can efficiently check if a node has been visited before, indicating the start of a cycle.

Let’s look at how the implementation of the algorithm works:

Initialization: Create an empty set called visited to store the nodes that have been seen.
Traversal: Start traversing the linked list from the head node. For each node:
1. If the node is already in the visited set, a cycle is detected, and return the current node as the start of the cycle.
2. If the node is not in the visited set, add it to the set. Move to the next node in the list.
End of list: If the traversal reaches the end of the list, return null, as there is no cycle in the linked list.

Let’s look at the illustration below to better understand the solution:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class LinkedList:
    def __init__(self):
        self.head_node = None
    def get_head(self):
        return self.head_node
    def is_empty(self):
        if self.head_node is None:
            return True
        else:
            return False
    def insert_at_head(self, dt):
        temp_node = Node(dt)
        temp_node.next = self.head_node
        self.head_node = temp_node
        return self.head_node
    def length(self):
        curr = self.get_head()
        length = 0
        
        while curr is not None:
            length += 1
            curr = curr.next
        return length        
def detectCycle(head):
    visited = set()
    node = head
    while node is not None:
        # If the current node is already in the visited set, a cycle is detected
        if node in visited:
            return node
        else:
            # Add the current node to the visited set
            visited.add(node)
            # Move to the next node in the list
            node = node.next
    return None
# Driver code
def main():
    # Initialize a linked list and add values
    lst = LinkedList()
    lst.insert_at_head(1)
    lst.insert_at_head(2)
    lst.insert_at_head(3)
    lst.insert_at_head(4)
    lst.insert_at_head(5)
    lst.insert_at_head(6)
    lst.insert_at_head(7)
    lst.insert_at_head(8)
    lst.insert_at_head(9)
    head = lst.get_head()
    node = lst.get_head()
    # Add cycle to the list 
    target_node = None
    for i in range(9):
        if node.data == 4:
            target_node = node
        if node.next is None:
            node.next = target_node
            break
        node = node.next
    print("Loop exists at the node with data: ", detectCycle(head).data)
if __name__ == "__main__":
    main()

Linked List Cycle II

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is the linked list cycle?

A linked list cycle occurs when a node in the list points back to a previously visited node, forming a loop. This prevents the list from terminating, leading to infinite traversal.

What is the start of a linked list?

The start of a linked list is the first node, often referred to as the “head” node. It is the entry point for accessing and traversing the entire list.

What is the starting point of the loop?

The starting point of the loop is the node where the cycle begins. It’s the node where the next pointer points back to a previously visited node, creating the loop.