Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

LinklistLoopNode.scala

import scala.annotation.tailrec

/**
  * Given a circular linked list, implement an algorithm that returns
  * the node at the beginning of the loop.
  *
  * Time Complexity O(n) and Space Complexity O(n)
  *
  * Created by Arun Sethia on 7/23/18.
  */

trait CircularLinklist {

  /**
    * abstract Node
    */
  abstract class AbstractNode {
    def data: Int

    def next: AbstractNode
  }

  /**
    * Nil Node to indicate end of link list
    */
  object NilNode extends AbstractNode {
    def data = -1

    override def toString() = s"Nil"

    lazy val next = throw new UnsupportedOperationException("tail of empty list")
  }


  /**
    * Circular node in lazy way to keep next node
    *
    * @param data
    * @param n
    */
  class CircularNode(val data: Int, n: => AbstractNode) extends AbstractNode {
    lazy val next = n

    override def toString() = s"data: ${data} "
  }

  /**
    * does loop exist if yes then return node at the beginning of the loop
    *
    * @param node
    * @return
    */
  def findLoopNode(node: AbstractNode) = {
    @tailrec
    def loopTraverse(s: AbstractNode, f: AbstractNode, visitedNode: Set[AbstractNode]): AbstractNode = {
      if (f == NilNode || f.next == NilNode) NilNode
      else {
        f.next.next match {
          case NilNode => NilNode
          case n: AbstractNode => {
            if (visitedNode.exists(_ == f) && s == f) f
            else loopTraverse(s.next, f.next.next, visitedNode + s)
          }
        }
      }
    }
    if (node == NilNode || node.next == NilNode) node
    else {
      loopTraverse(node, node.next, Set(node))
    }
  }

}

object LinklistLoopNode extends App with CircularLinklist {

  val node1: AbstractNode = new CircularNode(1, node2)
  val node2: AbstractNode = new CircularNode(2, node3)
  val node3: AbstractNode = new CircularNode(3, node4)
  val node4: AbstractNode = new CircularNode(4, node5)
  val node5: AbstractNode = new CircularNode(5, node3)

  val loopNode = findLoopNode(node1)

  println(loopNode.toString)

}