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

LinkRemoveMiddleSpec.scala

import org.scalatest.{Matchers, WordSpec}

/**
  * Implement an algorithm to remove the middle element of a singly linked list.
  * and return new linklist
  * time complexity O(n)
  * space complexity O(n/2)
  * 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 prevNode
    */
  implicit class NodeAddItem(prevNode: AbstractNode) {
    def prependItem(v: Int): AbstractNode = Node(v, prevNode)
  }

  /**
    * concenate two nodes node2 --> node1
    *
    * @param node1
    */
  implicit class Concenate(node1: AbstractNode) {
    /**
      * prepand node2 with node1
      *
      * @param node2
      * @return
      */
    def prepand(node2: AbstractNode): AbstractNode = {
      if (node2.next != NilNode) prepand(node2.next).prepand(Node(node2.data, NilNode))
      else Node(node2.data, node1)
    }

    /**
      * append list of nodes with node1
      *
      * @param listOfNodes
      * @return
      */
    def append(listOfNodes: List[AbstractNode]): AbstractNode = {
      val firstHalfNode: AbstractNode = listOfNodes.reduceLeft[AbstractNode]((a, b) => a.prepand(b))
      node1.prepand(firstHalfNode)
    }
  }

  /**
    * remove middle element of a singly linked list
    * time complexity O(n)
    * space complexity O(n)
    *
    * @param node
    * @return
    */
  def removeMiddleElement(node: AbstractNode): AbstractNode = {
    def removeMidElement(fastForwardPointer: AbstractNode, slowPointer: AbstractNode, acc: List[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.next.append(acc)
        case node: AbstractNode => node.next match {
          //if it has reached to last one then slow pointer is at middle
          //send slow pointer as middle
          case NilNode => slowPointer.next.append(acc)
          case _ => removeMidElement(fastForwardPointer.next.next, slowPointer.next, Node(slowPointer.data, NilNode) :: acc) //else keep finding
        }
      }
    }
    if (node == NilNode | (node.next == NilNode) | (node.next.next == NilNode)) {
      NilNode
    } else {
      removeMidElement(node, node, Nil)
    }
  }
}

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

  "find middle element " should {
    "remove middle element 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)

      //7->6-->5-->3-->2-->1-->Nil
      val result =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)
          .prependItem(5)
          .prependItem(6)
          .prependItem(7)
      assert(removeMiddleElement(linkList) == result)
    }
    "remove middle element 3" in {
      //5-->4-->3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)
          .prependItem(4)
          .prependItem(5)

      //5-->4-->2-->1-->Nil
      val result: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(4)
          .prependItem(5)

      assert(removeMiddleElement(linkList) == result)
    }
    "remove middle element 2" in {
      //3-->2-->1-->Nil
      val linkList: AbstractNode =
        Node(1, NilNode)
          .prependItem(2)
          .prependItem(3)

      //3-->1-->Nil
      val result: AbstractNode =
        Node(1, NilNode)
          .prependItem(3)

      assert(removeMiddleElement(linkList) == result)
    }
  }
}