Python Program to Detect Loop in Linked List

Use Floyd’s Cycle Detection algorithm with two pointers moving at different speeds; if they meet, a loop exists. In Python, create two pointers slow and fast, move slow by one step and fast by two steps, and check if they meet to detect a loop.

Examples

InputLinked list: 1 -> 2 -> 3 -> 4 -> 5 -> None

OutputNo loop detected

InputLinked list: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (loop back to node with value 3)

OutputLoop detected

InputLinked list: None (empty list)

OutputNo loop detected

How to Think About It

To detect a loop in a linked list, imagine two runners on a track: one runs slowly, the other runs fast. If the track is circular (loop), the fast runner will eventually catch the slow runner. If the fast runner reaches the end (None), there is no loop.

Algorithm

1

Start two pointers at the head of the linked list: slow and fast.

2

Move slow pointer one step forward and fast pointer two steps forward.

3

If fast or fast.next becomes None, return no loop detected.

4

If slow and fast pointers meet at any node, return loop detected.

Code

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_loop(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return "Loop detected"
    return "No loop detected"

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# Creating a loop for testing
head.next.next.next.next.next = head.next.next  # 5 -> 3
print(detect_loop(head))

Output

Loop detected

Dry Run

Let's trace the linked list with nodes 1->2->3->4->5 and a loop from 5 back to 3 through the code.

1

Initialize pointers

slow = Node(1), fast = Node(1)

2

First iteration

slow moves to Node(2), fast moves to Node(3)

3

Second iteration

slow moves to Node(3), fast moves to Node(5)

4

Third iteration

slow moves to Node(4), fast moves to Node(4) (because of loop)

5

Pointers meet

slow == fast at Node(4), loop detected

Iteration	Slow Pointer	Fast Pointer
Start	1	1
1	2	3
2	3	5
3	4	4

Why This Works

Step 1: Two pointers move at different speeds

The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

Step 2: If no loop, fast pointer reaches end

If the linked list has no loop, the fast pointer will reach None and the function returns no loop.

Step 3: If loop exists, pointers meet

If there is a loop, the fast pointer will eventually catch up to the slow pointer inside the loop, confirming a cycle.

Alternative Approaches

Using a set to track visited nodes

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_loop(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return "Loop detected"
        visited.add(current)
        current = current.next
    return "No loop detected"

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head.next.next
print(detect_loop(head))

This method uses extra memory to store visited nodes but is easier to understand.

Modifying node data temporarily (not recommended)

python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def detect_loop(head):
    current = head
    while current:
        if hasattr(current, 'visited'):
            return "Loop detected"
        setattr(current, 'visited', True)
        current = current.next
    return "No loop detected"

# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head.next.next
print(detect_loop(head))

This approach changes the nodes themselves, which can cause side effects and is not safe for all cases.

Complexity: O(n) time, O(1) space

Time Complexity

The algorithm visits each node at most a constant number of times, so it runs in linear time relative to the number of nodes.

Space Complexity

Only two pointers are used, so the space used is constant, regardless of list size.

Which Approach is Fastest?

Floyd’s Cycle Detection is fastest and uses least memory compared to using a set or modifying nodes.

Approach	Time	Space	Best For
Floyd’s Cycle Detection	O(n)	O(1)	Efficient detection without extra memory
Using a set	O(n)	O(n)	Simple to understand but uses extra memory
Modifying node data	O(n)	O(1)	Unsafe, can cause side effects