Skip to content

Instantly share code, notes, and snippets.

@pathikrit
Last active September 17, 2021 02:02
Show Gist options
  • Save pathikrit/4af1c1c2c590c2478b0f to your computer and use it in GitHub Desktop.
Save pathikrit/4af1c1c2c590c2478b0f to your computer and use it in GitHub Desktop.
Reverse a LinkedList in Scala
case class Node(value: Int, next: Option[Node])
def reverse(node: Node, prev: Option[Node] = None): Node = {
val reversed = node.copy(next = prev)
node.next map {reverse(_, Some(reversed))} getOrElse reversed
}
/****************************************************************/
val one = Node(1,Some(Node(2,Some(Node(3,None)))))
println(s"$one\n${reverse(one)}")
@pathikrit
Copy link
Author

To use the tail-recursion annotation, we need to write the above as:

@scala.annotation.tailrec
def reverse(node: Node, prev: Option[Node] = None): Node = {
  val reversed = node.copy(next = prev)
  node.next match {
    case None => reversed 
    case Some(next) => reverse(next, Some(reversed))  
  }  
} 

@pathikrit
Copy link
Author

And, lastly, here's a one liner:

case class Node(value: Int, next: Option[Node]) {
  def reverse(prev: Option[Node] = None): Node = next.fold(copy(next = prev))(_.reverse(Some(copy(next = prev))))
} 
/****************************************************************/
val one = Node(1,Some(Node(2,Some(Node(3,None)))))
println(s"$one\n${one.reverse()}")

@nsfyn55
Copy link

nsfyn55 commented Apr 26, 2015

You know List itself is a LinkedList.

def reverse[T](xs: List[T]): List[T] = xs match {
     case List() => List()
     case x :: xs1 => reverse(xs1) ::: List(x)
}

@v66moroz
Copy link

I would suggest using different structure for your linked list, Option reminds me null in this context.

sealed trait MyList[+A] {
  def reverse = {
    @annotation.tailrec
    def reverse_r[A](xs: MyList[A], acc: MyList[A]): MyList[A] = {
      xs match {
        case Empty          => acc
        case Node(v, next)  => reverse_r(next, Node(v, acc))
      }
    }
    reverse_r(this, Empty)
  }
}

case object Empty extends MyList[Nothing]

case class Node[A](value: A, next: MyList[A]) extends MyList[A]

Node(1, Node(2, Node(3, Empty))).reverse        //> res0: T.MyList[Int] = Node(3,Node(2,Node(1,Empty)))
Empty.reverse                                   //> res1: T.MyList[Nothing] = Empty

@pathikrit
Copy link
Author

@nsfyn55: This was a interview question where each node was presented in Java as:

public class Node(int value, Node next) {}

@v66moroz: Yes, ADTs make more sense here but this was presented in an interview with above Java class as example. I adapted it to Scala.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment