reverse linkedlist

reverse_linkedlist.scala

import scala.annotation.tailrec

object Main extends App {
  sealed trait Node
  case class Branch(value: Int, next: Node) extends Node
  case class Leaf(value: Int) extends Node

  def reverse: Node => Node = {
    case Branch(value, next) => _reverse(Leaf(value), next)
    case l @ Leaf(_)         => l
  }

  @tailrec
  def _reverse(n1: Node, n2: Node): Node = {
    n2 match {
      case Branch(v1, next) =>
        _reverse(Branch(v1, n1), next)
      case Leaf(value) =>
        Branch(value, n1)
    }
  }

  println(reverse(Branch(1, Branch(2, Branch(3, Leaf(4))))))
}