Educative: Interactive Courses for Software Developers

Statement#

Check whether or not a linked list contains a cycle. If a cycle exists, return TRUE. Otherwise, return FALSE. The cycle means that at least one node can be reached again by traversing the next pointer.

Constraints:

Let n be the number of nodes in a linked list.

$0\leq$ n $\leq500$
$-10^5 \leq$ Node.data $\leq 10^5$

Solution#

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow, based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach is to traverse the linked list and store the current node in a hash set. At each iteration, we check if the current node is already present in the hash set. If it is, we’ve found a cycle and return TRUE. Otherwise, we add the node to the hash set. If the traversal has been completed, return FALSE, since we’ve reached the end of the linked list without encountering a cycle.

The time complexity is $O(n)$ , since we only traverse the linked list once, where $n$ represents the total number of nodes in a linked list. The space complexity of the naive approach is also $O(n)$ , since in the worst case, we store $n$ nodes in the hash set.

Optimized approach using fast and slow pointers#

This problem can be solved efficiently using the fast and slow pointers technique, where the fast pointer moves two steps, and the slow pointer moves one step in the linked list.

If there is no cycle in the linked list, the fast pointer will reach the end of the linked list before the slow pointer. If there is a cycle, the fast pointer will eventually catch up to the slow pointer, since it is moving faster. When this happens, we know that we have a cycle in the linked list. The following steps can be performed to implement the algorithm above:

We initialize two pointers, fast and slow, which point to the head of the linked list.
We traverse the linked list using these two pointers. They move in the following way:
- The slow pointer moves only one node forward in each iteration.
- The fast pointer moves two nodes forward in each iteration, which means that it skips a node.
If the fast pointer becomes NULL, we have reached the end of the linked list. Since no cycle exists, return FALSE.
If both slow and fast pointers become equal to each other, return TRUE, since a cycle exists in the linked list.

Here’s a demonstration of the algorithm above:

main.py

linked_list_node.py

linked_list.py

print_list.py

from linked_list import LinkedList
from print_list import *
def detect_cycle(head):
    if head is None:
        return False
    slow, fast = head, head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False
# Driver code
def main():
    input = (
             [2, 4, 6, 8, 10, 12],
             [1, 3, 5, 7, 9, 11],
             [0, 1, 2, 3, 4, 6],
             [3, 4, 7, 9, 11, 17],
             [5, 1, 4, 9, 2, 3],
            )
    pos = [0, -1, 1, -1, 2]
    j = 1

Enter to Rename, Shift+Enter to Preview

Linked List Cycle

Solution summary#

To recap, the solution to this problem can be divided into the following three parts:

Initialize both the slow and fast pointers to the head node.
Move both pointers at different rates, i.e. the slow pointer will move one step ahead whereas the fast pointer will move two steps.
If both pointers are equal at some point, we know that a cycle exists.

Time complexity#

The time complexity of the algorithm is $O(n)$ , where $n$ is the number of nodes in the linked list.

Space complexity#

The space complexity of the algorithm above is $O(1)$ .

Solution: Linked List Cycle