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

LinklistIntersection.scala

package linklist4

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+m) 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} "
  }

  /**
    * implicit class provides various util functions
    *
    * @param node
    */
  implicit class NodeUtils(node: AbstractNode) {
    def len = findLength(node)
  }

  /**
    * find lenght of a given List
    *
    * @param list
    * @return
    */
  def findLength(list: AbstractNode): Int = {
    def length(node: AbstractNode, count: Int): Int = {
      node.next match {
        case NilNode => count
        case _ => length(node.next, count + 1)
      }
    }
    length(list, 0)
  }

  /**
    * find intersection of list1 and list2
    *
    * @param list1
    * @param list2
    * @return
    */
  def findIntersection(list1: AbstractNode, list2: AbstractNode): AbstractNode = {
    //find difference between two list, long and short linklist
    val (longlist, shortlist, diff) = compareLongShort(list1, list2)
    //move longer list to number of difference nodes,
    //so longlist and shortlist will have same number of nodes
    val afterMoveLong = skipNodes(diff, longlist)
    //now afterMoveLong which is made from longlist and
    @tailrec
    def intersectionNode(l1: AbstractNode, l2: AbstractNode): AbstractNode = {
      if (l1 == l2) l1
      else intersectionNode(l1.next, l2.next)
    }
    intersectionNode(afterMoveLong, shortlist)
  }

  /**
    * this will return long list, shortlist and different in length
    *
    * @param list1
    * @param list2
    * @return
    */
  private def compareLongShort(list1: AbstractNode, list2: AbstractNode): (AbstractNode, AbstractNode, Int) = {
    val len1 = list1.len
    val len2 = list2.len
    //find difference between two list
    if (len1 > len2) {
      (list1, list2, (len1 - len2))
    } else {
      (list2, list1, (len2 - len1))
    }
  }

  /**
    * move to next node for given numberOfTimes
    *
    * @param numberOfTime
    * @param node
    * @return
    */
  @tailrec
  final def skipNodes(numberOfTime: Int, node: AbstractNode): AbstractNode = {
    if (numberOfTime == 0) node
    else skipNodes(numberOfTime - 1, node.next)
  }

}

object LinklistIntersection extends App with CircularLinklist {

  //1-->2-->3-->4-->5-->6-->NilNode
  val list1: 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, node6)
  val node6: AbstractNode = new CircularNode(6, NilNode)

  //7-->8-->5-->6-->NilNode
  val list2: AbstractNode = new CircularNode(7, node22)
  val node22: AbstractNode = new CircularNode(8, node5)

  //intersection will be 5
  println(findIntersection(list1, list2))
}