Cycle Detection in Linked Lists

by

Problem Description: A cycle in a linked list occurs when a node’s next pointer points back to one of the previous nodes, creating a loop. This means traversing the linked list will not end; it will keep looping indefinitely. Detecting such cycles is an important task in linked list operations, particularly when dealing with dynamic memory or linked data structures.

Key Idea: The most common and efficient algorithm for detecting a cycle in a linked list is Floyd’s Cycle Detection Algorithm (also known as the “Tortoise and Hare” algorithm). This algorithm uses two pointers:

  • A slow pointer (slow), which moves one step at a time.
  • A fast pointer (fast), which moves two steps at a time.

If there is a cycle, the fast pointer will eventually meet the slow pointer. If there is no cycle, the fast pointer will reach the end of the linked list.

Example

Example 1: Linked List with a Cycle

Consider the linked list:

1 -> 2 -> 3 -> 4 -> 5
                ^                |
                 |________|

Here, the 5 node points back to the 3 node, creating a cycle. The algorithm should detect this.

Example 2: Linked List without a Cycle

1 -> 2 -> 3 -> 4 -> 5 -> null

Here, the 5 node points to null. The algorithm should confirm there is no cycle.

Kotlin Solution

Below is a Kotlin implementation of the cycle detection algorithm:

Kotlin
class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun hasCycle(head: ListNode?): Boolean {
    if (head == null || head.next == null) return false

    var slow = head
    var fast = head

    while (fast != null && fast.next != null) {
        slow = slow?.next          // Move slow pointer by 1 step
        fast = fast.next?.next     // Move fast pointer by 2 steps

        if (slow == fast) {
            // Cycle detected
            return true
        }
    }

    // No cycle
    return false
}

fun main() {
    // Example 1: Linked List with a Cycle
    val node1 = ListNode(1)
    val node2 = ListNode(2)
    val node3 = ListNode(3)
    val node4 = ListNode(4)
    val node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node3 // Creates a cycle

    println("Does the list have a cycle? ${hasCycle(node1)}") // Output: true

    // Example 2: Linked List without a Cycle
    val nodeA = ListNode(1)
    val nodeB = ListNode(2)
    val nodeC = ListNode(3)
    nodeA.next = nodeB
    nodeB.next = nodeC

    println("Does the list have a cycle? ${hasCycle(nodeA)}") // Output: false
}

Explanation of the Code

  1. Node Definition:
    • A ListNode class is defined, which has a value (value) and a reference to the next node (next).
  2. Cycle Detection Function:
    • The function hasCycle takes the head of the linked list as input.
    • It uses two pointers (slow and fast).
    • A while loop is used to traverse the list. If fast or fast.next is null, there is no cycle.
    • If slow equals fast, a cycle is detected.
  3. Test Cases in main:
    • Two examples are tested: one with a cycle and one without a cycle.

Complexity Analysis

  • Time Complexity: O(n)O(n)O(n), where nnn is the number of nodes. Both pointers traverse the list at most once.
  • Space Complexity: O(1)O(1)O(1), as no extra space is used apart from pointers.

This efficient solution ensures quick detection of cycles in linked lists and is widely used in practice.

Leave a Comment