I have 2 linked lists in scala with following node class definition:

class node(_x: Int = 0, nxt: node = null) {
    var x = _x
    var next = nxt
}

I want to merge two linked lists (which will be in ascending sort order) into a third sorted list. What is the best way to do this in Scala.

My solution:

object Solution {
    def mergeTwoLists(list1: node, list2: node): node = {
        (list1.x >= list2.x) match {
            case true => ListNode(list2.x, mergeTwoLists(list1, list2.next))
            case false => ListNode(list1.x, mergeTwoLists(list2, list1.next))
        }
    }
}

however, when I run this, I get nullPointerException for following 2 lists [1,2,4] [1,3,4]

CodePudding user response：

If you put a println((list1, list2)) at the start of your function, you'll see that at some point you're comparing Node(4,null) to null.

Before fixing it, your code is full of code smells and things that don't follow Scala best practices:

• In Scala, you shouldn't really ever get a NullPointerException because you should never intentionally use null. That's what Options are for.
• Use capital letters when defining classes (i.e. Node over node).
• Your class definition is far too Java-y and over-complicated. It can be simplified to case class Node(x: Int = 0, next: Node = null) (ignoring the incorrect use of null) without the private/public variable stuff.
• Your function has an unnecessary pattern match in it - nothing technically wrong with it, but it's a bit weird (note: subjective) to match on true/false instead of using an if statement.

So to re-write your (still broken) function, it would look more like this:

case class Node(x: Int = 0, next: Node = null)

def mergeTwoLists(list1: Node, list2: Node): Node = {
  if (list1.x >= list2.x) {
    Node(list2.x, mergeTwoLists(list1, list2.next))
  } else {
    Node(list1.x, mergeTwoLists(list2, list1.next))
  }
}

mergeTwoLists(Node(1, Node(2, Node(4))), Node(1, Node(3, Node(4))))

On to fixing it:

• Change the class definition to make the second parameter optional (to avoid null):

case class Node(x: Int = 0, next: Option[Node] = None)

• Change your function to make the second parameter optional to account for this:

def mergeTwoLists(list1: Node, list2: Option[Node]): Node = {
  ???
}

• You need to know if the second list is present or not. If it's None, just return the first list. Otherwise, carry on:

def mergeTwoLists(list1: Node, list2: Option[Node]): Node = {
  list2 match {
    case None => list1
    case Some(list) => ???
  }
}

• Finally, modify your original if/else to account for the new optional second parameter in the Node:

def mergeTwoLists(list1: Node, list2: Option[Node]): Node = {
  list2 match {
    case None => list1
    case Some(list) =>
      if (list1.x >= list.x) {
        Node(list.x, Some(mergeTwoLists(list1, list.next)))
      } else {
        Node(list1.x, Some(mergeTwoLists(list, list1.next)))
      }
  }
}

Now, if you pass in your inputs you'll get a more sensible output:

mergeTwoLists(
  Node(1, Some(Node(2, Some(Node(4))))),
  Some(Node(1, Some(Node(3, Some(Node(4))))))
)

outputs

Node(1,Some(Node(1,Some(Node(2,Some(Node(3,Some(Node(4,Some(Node(4,None)))))))))))

Note: I don't know if this is the "best" way but it's how to solve your problem with the function you've given already. I'd also consider renaming the variables as list1, list2 and list are a bit confusing.

Scastie of it working: https://scastie.scala-lang.org/tUPoVzKpRRSJjZz62KsmhQ