Implement an algorithm to find the middle element of a singly linked list.

LinklistMiddleSpec.scala

import org.scalatest.{Matchers, WordSpec}

/**
  * Implement an algorithm to find the middle element of a singly linked list.
  * time complexity O(n)
  * space complexity O(1)
  * Created by Arun Sethia on 7/17/18.
  */
trait Linklist {

  /**
    * 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"

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

  /**
    * Node class
    *
    * @param data
    * @param next
    */
  case class Node(data: Int, next: AbstractNode) extends AbstractNode {
    override def toString() = s"data: ${data} next: ${next}"
  }

  /**
    * add new node in the beginning
    *
    * @param head
    */
  implicit class NodeAdd(head: AbstractNode) {
    def prependItem(v: Int): AbstractNode = Node(v, head)
  }

   /**
    * find middle element of a singly linked list
    * time complexity O(n)
    * space complexity O(1)
    *
    * @param node
    * @return
    */
  def findMiddleElement(node: AbstractNode) = {
    def findMidElement(fastForwardPointer: AbstractNode, slowPointer: AbstractNode): AbstractNode = {
      fastForwardPointer match {
        //if not reached to the last one then check might be second last one,
        // that will be the case in even elements in linked list
        case NilNode => slowPointer
         //if it has reached to last one then slow pointer is at middle
        //send slow pointer as middle
        case node: AbstractNode => node.next match {
          case NilNode => slowPointer //send slow pointer as middle 
          case _ => findMidElement(fastForwardPointer.next.next, slowPointer.next) //else keep finding
        }
      }
    }
    if (node == NilNode | (node.next == NilNode) | (node.next.next == NilNode)) {
      -1
    } else {
      findMidElement(node, node).data
    }
  }

/**
  * test cases for kth last element
  */
class LinklistMiddleSpec extends WordSpec
  with Matchers
  with Linklist {

  "find middle element " should {
    "return mid element as 4" in {
      //7->6-->5-->4-->3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)
          .prependItem(4)
          .prependItem(5)
          .prependItem(6)
          .prependItem(7)
      assert(findMiddleElement(linkList) == 4)
    }
    "return mid element as 3" in {
      //5-->4-->3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)
          .prependItem(4)
          .prependItem(5)

      assert(findMiddleElement(linkList) == 3)
    }
    "return mid element as 2" in {
      //3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)

      assert(findMiddleElement(linkList) == 2)
    }
    "return mid element as 2 for even elements" in {
      //3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)
          .prependItem(4)
      assert(findMiddleElement(linkList) == 2)
    }
    "return mid element as 1" in {
      //3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
      assert(findMiddleElement(linkList) == -1)
    }
  }
}