138. Copy List with Random Pointer

leetcode-138.scala

/**
 * Definition for a Node.
 * class Node(var _value: Int) {
 *   var value: Int = _value
 *   var next: Node = null
 *   var random: Node = null
 * }
 */

import scala.collection.mutable._

object Solution {
  def copyRandomList(head: Node): Node = {
    val nodes = ArrayBuffer.empty[Node]
    val indexed = HashMap.empty[Node, Int]
    if (head == null) null
    else {
      var curr = head
      var index = 0

      indexed += (curr -> index)
      index += 1

      var newCurr: Node = new Node(curr.value)
      newCurr.random = curr.random
      val newHead: Node = newCurr
      nodes += newCurr

      curr = curr.next
      while (curr != null) {
        indexed += (curr -> index)
        index += 1

        val prev = newCurr
        newCurr = new Node(curr.value)
        newCurr.random = curr.random
        prev.next = newCurr
        nodes += newCurr
        curr = curr.next
      }

      newCurr = newHead
      while (newCurr != null) {
        newCurr.random = if (newCurr.random == null) null else nodes(indexed(newCurr.random))
        newCurr = newCurr.next
      }
      newHead
    }
  }

}