Detect Loop in Linked List in Kotlin

To detect a loop in a linked list, you can use the Floyd’s cycle-finding algorithm, also known as the “tortoise and hare” algorithm.

This algorithm works by using two pointers – a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there is a loop in the linked list, the fast pointer will eventually catch up to the slow pointer and they will meet.

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

Node class to represent each node in the linked list, which contains a value and a reference to the next node.

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

    var slow = head
    var fast = head.next

    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false
        }
        slow = slow?.next
        fast = fast.next?.next
    }

    return true
}

The hasCycle function takes a head node as input and returns a boolean indicating whether there is a loop in the linked list. It first checks if the linked list is empty or has only one node, in which case there can’t be a loop and it returns false.

Otherwise, it initializes two pointers – a slow pointer and a fast pointer – to the head and head.next nodes, respectively. It then enters a loop where the slow pointer moves one step at a time, and the fast pointer moves two steps at a time. If there is a loop, the fast pointer will eventually catch up to the slow pointer and they will meet at some node inside the loop. If there is no loop, the fast pointer will reach the end of the linked list and we will return false.

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

fun hasCycle(head: Node?): Boolean {
    if (head == null || head.next == null) {
        return false
    }
    
    var slow = head
    var fast = head.next
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false
        }
        slow = slow?.next
        fast = fast.next?.next
    }
    
    return true
}

fun main() {
    val head = Node(1)
    head.next = Node(2)
    head.next?.next = Node(3)
    head.next?.next?.next = Node(4)
    head.next?.next?.next?.next = head.next // create a loop
    
    println(hasCycle(head)) // should print true
    
    head.next?.next?.next?.next = null // remove the loop
    
    println(hasCycle(head)) // should print false
}

In the main function, we create a linked list with four nodes and create a loop by making the last node point to the second node. We then call the hasCycle function to check if there is a loop, and print the result. We then remove the loop by making the last node point to null, and call the hasCycle function again to check that it returns false.