Starting Node of a Loop in Linked List in Kotlin

by

What is Loop in Linked List ?

In a linked list, a loop occurs when there is a cycle in the nodes that creates an infinite loop. A loop can occur if a node points to a previous node in the list or if multiple nodes point to the same node in the list. Here’s an example of a linked list with a loop:

1 -> 2 -> 3 -> 4 -> 5 -> 6
                       ^              |
                        |              v
                       9 <- 8 <- 7

In this example, the node with value 4 points to the node with value 9, which is a previous node in the list. The node with value 7 points to the node with value 9, creating a cycle in the list. This cycle creates an infinite loop where the list can never be fully traversed.

To detect the starting node of a loop in a linked list, we can use Floyd’s cycle-finding algorithm, also known as the “tortoise and hare” algorithm. Here are the steps:

  1. Initialize two pointers, slow and fast, to the head of the linked list.
  2. Move the slow pointer one node at a time, and move the fast pointer two nodes at a time.
  3. If the fast pointer ever reaches the end of the list (i.e., it points to null), there is no loop in the list, and we can exit the algorithm.
  4. If there is a loop in the list, the fast pointer will eventually catch up to the slow pointer. When this happens, we know that the fast pointer has traveled exactly twice as far as the slow pointer, and has gone around the loop one or more times.
  5. Reset the slow pointer to the head of the list, and leave the fast pointer where it is. Then, move both pointers one node at a time until they meet. The node they meet at is the starting node of the loop.

here’s Kotlin code that detects the starting node of a loop in a linked list using Floyd’s cycle-finding algorithm:

Kotlin
class Node(var value: Int) {
    var next: Node? = null
}
fun detectLoopStart(head: Node?): Node? {
    var slow = head
    var fast = head
    // Step 1: Find if there's a loop in the linked list
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow == fast) {
            break
        }
    }
    // Step 2: If there's no loop, return null
    if (fast?.next == null) {
        return null
    }
    // Step 3: Reset the slow pointer to the head and keep the fast pointer where it is
    slow = head
    // Step 4: Move both pointers one node at a time until they meet at the start of the loop
    while (slow != fast) {
        slow = slow?.next
        fast = fast?.next
    }
    // Step 5: Return the starting node of the loop
    return slow
}
fun main() {
    // Create a linked list with a loop
    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)
    head.next?.next?.next?.next?.next = Node(6)
    head.next?.next?.next?.next?.next?.next = Node(7)
    head.next?.next?.next?.next?.next?.next?.next = Node(8)
    head.next?.next?.next?.next?.next?.next?.next?.next = Node(9)
    head.next?.next?.next?.next?.next?.next?.next?.next?.next = head.next?.next?.next
    // Detect the starting node of the loop
    val loopStart = detectLoopStart(head)
    // Print the value of the starting node of the loop
    println("Starting node of loop: ${loopStart?.value}")
}

Steps of the detectLoopStart function :

  1. Initialize two pointers, slow and fast, to the head of the linked list.
    • The slow pointer will move one node at a time, while the fast pointer will move two nodes at a time.
  2. Move the slow and fast pointers through the list until the fast pointer catches up to the slow pointer or reaches the end of the list.
    • If the fast pointer reaches the end of the list, there is no loop in the list, and we can exit the function.
    • If the fast pointer catches up to the slow pointer, we have found a loop in the list.
  3. Reset the slow pointer to the head of the list, and leave the fast pointer where it is.
  4. Move both pointers one node at a time until they meet.
    • The node they meet at is inside the loop.
  5. Reset the slow pointer to the head of the list, and leave the fast pointer where it is.
  6. Move both pointers one node at a time until they meet.
    • The node they meet at is the starting node of the loop.
  7. Return the starting node of the loop.

In the example above, the detectLoopStart function correctly detects and returns the starting node of the loop in the linked list.

The output of the main function is: Starting node of loop: 4

The time complexity of the detectLoopStart function is O(n), where n is the number of nodes in the linked list. This is because we need to traverse the entire linked list to find the loop, and then traverse the loop once to find the starting node.

The space complexity of the function is O(1), because we are only using a constant amount of extra space to store the slow and fast pointers. We are not using any data structures like arrays or hash tables to store the nodes, so the space required by the function does not depend on the size of the input.

Leave a Comment