Cycle detection algorithm in Scala

In computer science, detecting a cycle in a linked list is a classic problem. Cycles in linked lists can cause infinite loops in your code and lead to memory inefficiency. Today, we'll discuss how to detect a cycle in a linked list using Scala with the help of the two-pointer technique.

 

Below is a Scala implementation to solve the problem:

The Code

 

object Solution {

    def hasCycle(head: ListNode): Boolean = 

    {

      var p1 = head

      var p2 = head.next

      val x = true

 

      while (p1 != p2) {

        if (p1 == null || p2 == null) {

          return false

        }

 

        if (p2.next == null) {

          return false

        }

 

        p1 = p1.next

        p2 = p2.next.next

      }

 

      x

    }

}

1. Understanding the Two-Pointer Technique

 

The two-pointer technique involves using two pointers:

 

    p1: A slow pointer that moves one step at a time.

    p2: A fast pointer that moves two steps at a time.

 

If there’s a cycle in the linked list, the fast pointer (p2) will eventually meet the slow pointer (p1). If p1 and p2 point to the same node during iteration, it indicates the presence of a cycle.

2. Initialization

 

    p1 is initialized to head, the starting node of the linked list.

    p2 is initialized to head.next, the second node in the list.

 

3. Loop Condition

 

The while (p1 != p2) loop runs as long as the two pointers don’t meet. Inside the loop:

 

    If either p1 or p2 becomes null, it means there’s no cycle, and the function returns false.

    If p2.next is null, it also confirms the absence of a cycle.

 

4. Pointer Movement

 

    p1 moves one step forward (p1 = p1.next).

    p2 moves two steps forward (p2 = p2.next.next).

 

5. Returning Result

 

The variable x is returned after exiting the loop. However, this seems unnecessary, as x is always true. The function could directly return true when the loop exits.

Issues in the Code

 

While the logic is mostly correct, the code has a few issues:

 

    Returning x Always

        The variable x is redundant and not meaningful in this context.

        Instead, the function should return true when the loop exits.

    p2 Initialization

        The initialization of p2 as head.next may cause a NullPointerException if the input list is empty (head == null).

 

Here’s an improved version of the function:

 

object Solution {

    def hasCycle(head: ListNode): Boolean = {

        if (head == null || head.next == null) return false

 

        var p1 = head

        var p2 = head.next

 

        while (p1 != p2) {

            if (p1 == null || p2 == null || p2.next == null) {

                return false

            }

            p1 = p1.next

            p2 = p2.next.next

        }

 

        true // A cycle is detected

    }

}

 

Key Improvements

 

    Initial Null Check: The code checks whether the list is empty or has only one node before proceeding.

    Simplified Return: It directly returns true when a cycle is detected.

 

Example Usage

 

Here’s how you might test this function:

 

// Define the ListNode class

class ListNode(var value: Int = 0, var next: ListNode = null)

 

// Create a linked list with a cycle

val node1 = new ListNode(1)

val node2 = new ListNode(2)

val node3 = new ListNode(3)

node1.next = node2

node2.next = node3

node3.next = node1 // Cycle created

 

println(Solution.hasCycle(node1)) // Output: true

 

// Create a linked list without a cycle

val node4 = new ListNode(4)

val node5 = new ListNode(5)

node4.next = node5

 

println(Solution.hasCycle(node4)) // Output: false
 

 

Detecting a cycle in a linked list is an essential skill for working with data structures. Using the two-pointer technique is an efficient way to solve this problem in O(n) time complexity and O(1) space complexity.

 

For more articles on Scala programming and advanced algorithms, stay tuned to orientalguru.co.in!