Remove loop in Linked List in Kotlin

A loop in a linked list is a situation where a node in the list points to a previous node, causing the list to have a cycle. In other words, a loop occurs when there is at least one node in the list that can be reached by following a chain of next pointers starting from another node. Loops can cause problems in linked lists because they can create infinite loops when traversing the list, or they can cause algorithms that operate on linked lists to fail. Detecting and removing loops in linked lists is an important task in computer science and is often used in programming interview questions.

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

class ListNode(var value: Int) – This is a simple class to define the ListNode data structure for our linked list. It has a value field to store the integer value of the node, and a next field to point to the next node in the list.

fun detectAndRemoveLoop(head: ListNode?) {
    // Step 1: Detect the loop
    var slow = head
    var fast = head
    var loopDetected = false

fun detectAndRemoveLoop(head: ListNode?) – This is the main function that detects and removes a loop from a linked list. It takes the head of the linked list as input.

var slow = head – We start by initializing two pointers – slow and fast – both pointing to the head of the linked list.

while (fast?.next != null) {
    slow = slow?.next
    fast = fast.next?.next

    if (slow == fast) {
        loopDetected = true
        break
    }
}

while (fast?.next != null) – We then use the “slow and fast” pointer technique to detect the presence of a loop in the linked list. In each iteration of the loop, we move slow one node at a time and fast two nodes at a time. If there is a loop, the fast pointer will eventually catch up to the slow pointer.

if (slow == fast) {
    loopDetected = true
    break
}
}

if (slow == fast) – If there is a loop, we set the loopDetected flag to true and break out of the loop.

// Step 2: Find the start of the loop
if (loopDetected) {
    var p1 = head
    var p2 = slow

    while (p1 != p2) {
        p1 = p1?.next
        p2 = p2?.next
    }

    val startOfLoop = p1

    // Step 3: Remove the loop
    var prev = startOfLoop
    var current = startOfLoop!!.next

    while (current != null && current != startOfLoop) {
        prev = current
        current = current.next
    }

    prev!!.next = null
}

if (loopDetected) – If a loop was detected, we move one pointer (p1) to the beginning of the linked list and keep the other pointer (p2) at the point where the two pointers (slow and fast) met. We then move both pointers one node at a time until they meet again. The node at which they meet is the start of the loop.

val startOfLoop = p1 – We store the start of the loop in a variable called startOfLoop.

var prev = startOfLoop and var current = startOfLoop.next – We initialize two pointers – prev and current – to the node just after the start of the loop.

while (current != startOfLoop) – We then move both pointers one node at a time until current points to the node just before the start of the loop.

prev.next = null – Finally, we set the next field of the node just before the start of the loop to null, effectively removing the loop from the linked list.

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

fun findMiddleElement(head: Node?): Int? {
    var slowPtr = head
    var fastPtr = head

    while (fastPtr != null && fastPtr.next != null) {
        slowPtr = slowPtr?.next
        fastPtr = fastPtr.next?.next
    }

    return slowPtr?.data
}

fun main() {
    // create a linked list
    val 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)

    // find the middle element
    val middleElement = findMiddleElement(head)

    // print the middle element
    if (middleElement != null) {
        println("The middle element is $middleElement")
    } else {
        println("The linked list is empty")
    }
}

In this example, we create a linked list with a loop by setting the next field of the last node to point to the second node in the list. We then call the detectAndRemoveLoop() function to remove the loop from the linked list. Finally, we print the linked list to verify that the loop has been removed.