A slow Scala solution for https://leetcode.com/problems/lru-cache/

LRUCache.scala

import scala.collection.mutable

class LRUCache(_capacity: Int) {

  var head: Option[Int] = None
  var tail: Option[Int] = None
  var count = 0
  val cache = mutable.Map.empty[Int, Node]

  def get(key: Int): Int = {
    cache.get(key).map { n =>
      moveToEnd(key, n)
      n.value
    }.getOrElse(-1)
  }

  def put(key: Int, value: Int): Unit = {
    if (cache.contains(key)) {
      val n = cache(key).copy(value = value)
      cache += key -> n
      moveToEnd(key, n)
    } else {
      if (count >= _capacity) {
        head = head.flatMap { k =>
          val newHead = cache(k).next.map { nk =>
            cache += nk -> cache(nk).copy(prev = None)
            nk
          }
          cache -= k
          count -= 1
          newHead
        }
      }
      cache += key -> Node(tail, None, value))
      count += 1
      if (head.isEmpty) {
        head = Some(key)
      }
      tail.foreach { k =>
        cache += k -> cache(k).copy(next = Some(key))
      }
      tail = Some(key)
    }
  }

  private def moveToEnd(key: Int, n: Node): Unit = {
    if (count > 1 && n.next.nonEmpty) {
      n.prev.foreach { k =>
        cache += k -> cache(k).copy(next = n.next)
      }
      n.next.foreach { k =>
        cache += k -> cache(k).copy(prev = n.prev)
      }
      if (n.prev.isEmpty) {
        head = n.next
      }
      tail.foreach { k =>
        cache += k -> cache(k).copy(next = Some(key))
      }
      cache += key -> n.copy(prev = tail, next = None)
      tail = Some(key)
    }
  }
}

case class Node(prev: Option[Int], next: Option[Int], value: Int)