Detecting a Loop in a Linked List Using Go

In this tutorial, we will learn how to detect a loop in a linked list using the Go programming language. A loop in a linked list occurs when a node’s next pointer points back to one of the previous nodes in the list, forming a cycle.

Program Structure

The program is structured as follows:

• We define a Node struct representing each element in the linked list.
• We create a function detectLoop that uses Floyd’s Cycle-Finding Algorithm, also known as the “Tortoise and Hare” algorithm, to detect if a loop exists.
• The main function demonstrates the creation of a linked list, introduces a loop, and checks whether the loop is detected.

Go Program

// Node struct represents an element in the linked list
type Node struct {
    data int      // Data stored in the node
    next *Node    // Pointer to the next node
}

// detectLoop function uses Floyd's Cycle-Finding Algorithm to detect a loop
func detectLoop(head *Node) bool {
    slow := head   // Slow pointer moves one step at a time
    fast := head   // Fast pointer moves two steps at a time

    for slow != nil && fast != nil && fast.next != nil {
        slow = slow.next            // Move slow pointer by one
        fast = fast.next.next       // Move fast pointer by two

        if slow == fast {           // If they meet, there's a loop
            return true
        }
    }
    return false                     // No loop detected
}

// Main function to demonstrate the loop detection
func main() {
    // Creating nodes
    node1 := &Node{data: 1}
    node2 := &Node{data: 2}
    node3 := &Node{data: 3}
    node4 := &Node{data: 4}

    // Linking nodes
    node1.next = node2
    node2.next = node3
    node3.next = node4

    // Introducing a loop for testing (node4 points back to node2)
    node4.next = node2

    // Detect loop
    if detectLoop(node1) {
        println("Loop detected!")
    } else {
        println("No loop detected.")
    }
}

Explanation

In the detectLoop function, two pointers (slow and fast) are used. Both start at the head of the linked list:

• The slow pointer moves one step at a time.
• The fast pointer moves two steps at a time.

If the linked list contains a loop, the fast pointer will eventually meet the slow pointer within the loop. If they meet, we conclude that the list contains a loop and return true. If the fast pointer reaches the end of the list (fast == nil or fast.next == nil), then the list does not contain a loop, and the function returns false.

In the main function, we manually create a linked list with four nodes and introduce a loop by setting the next pointer of the last node to point back to one of the earlier nodes. The detectLoop function is then called to check if the loop is correctly identified.

Conclusion

This program effectively detects whether a loop exists in a linked list using a common algorithm. This method is efficient and runs in O(n) time complexity with O(1) space complexity, making it ideal for large linked lists.