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

LinklistKthLastSpec.scala

import org.scalatest.{Matchers, WordSpec}

/**
  * Implement an algorithm to find the kth to last 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 kth to last element of a singly linked list
    * time complexity O(n)
    * space complexity O(1)
    *
    * @param k
    * @param node
    * @return
    */
  def kthLastElement(k: Int, node: AbstractNode) = {
    def moveKth(mainPointer: Option[AbstractNode], refPointer: AbstractNode, count: Int): AbstractNode = {
      if (count == k && !mainPointer.isDefined) {
        //since it reached to desired distance so keep count as k
        moveKth(Some(node), refPointer, count)
      } else {
        refPointer.next match {
          case NilNode if (count < k) => NilNode
          case NilNode => mainPointer.get
          case h if (!mainPointer.isDefined) => moveKth(None, h, count + 1)
          //moving main pointer so increment on count,
          // not we just have to move refpoint till end kep moving mainpointer from beginning
          case h if (mainPointer.isDefined) => moveKth(Some(mainPointer.get.next), h, count)
        }
      }
    }
    if (node == NilNode || (node.next == NilNode && k > 1) || k < 1) {
      -1
    } else {
      moveKth(None, node, 1).data
    }
  }
}

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

  "given link list 6->5->4->3->2->1-Nil" should {
    //6-->5-->4-->3-->2-->1-->Nil
    val linkList: AbstractNode =
      Node(1, NilNode)
        .prependItem(2)
        .prependItem(3)
        .prependItem(4)
        .prependItem(5)
        .prependItem(6)

    "return last 3rd element" in {
      assert(kthLastElement(3, linkList) == 3)
    }
    "return last 4rd element" in {
      assert(kthLastElement(4, linkList) == 4)
    }
    "return last 1st element" in {
      assert(kthLastElement(1, linkList) == 1)
    }
    "return last 6st element" in {
      assert(kthLastElement(6, linkList) == 6)
    }
    "return last 7th element" in {
      assert(kthLastElement(7, linkList) == -1)
    }
    "return last 0th element" in {
      assert(kthLastElement(0, linkList) == -1)
    }
  }
}