Plus One Linked List: Functional Approach

user_4582374 0
Viewed 129

Been banging my head on this leetcode problem. Wondering if there is a functional way to approach this. All I can come up with is using mutable objects(In Scala).

Given a non-negative integer represented as a linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

Example 1:

Input: head = [1,2,3] Output: [1,2,4]

Example 2:

Input: head = [0] Output: [1]

Constraints:

The number of nodes in the linked list is in the range [1, 100].

0 <= Node.val <= 9

The number represented by the linked list does not contain leading zeros except for the zero itself.

 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def plusOne(head: ListNode): ListNode = {
        
    }
}

More interesting input/output = [1,9,9,9,9] => [2,0,0,0,0]

scala functional-programming
3 Answers

(tail) Recursion to the rescue!

type Digit = Int // Refined [1..9]
type Number = List[Digit]

def plusOne(number: Number): Number = {
  def sumDigits(d1: Digit, d2: Digit): (Digit, Digit) = {
    val r = d1 + d2
    (r % 10) -> (r / 10)
  }
  
  @annotation.tailrec
  def loop(remaining: Number, remainder: Digit, acc: Number): Number =
    remaining match {
      case digit :: digits =>
        val (result, newRemainder) = sumDigits(digit, remainder)
        loop(remaining = digits, newRemainder, result :: acc)
      
      case Nil =>
        if (remainder != 0) remainder :: acc
        else acc
    }
    
  loop(remaining = number.reverse, remainder = 1, acc = List.empty)
}

Which you can use like this:

plusOne(List(1, 2, 3))
// res: Number = List(1, 2, 4)

You can see the code running here.

user_41114040

Here's one approach:

class ListNode(_x: Int = 0, _next: ListNode = null) {
  var next: ListNode = _next
  var x: Int = _x
}

def toNode(l: List[Int]): ListNode = {
  l.foldRight[ListNode](null)((x, acc) => new ListNode(x, acc))
}

def toList(node: ListNode): List[Int] =
  Iterator.iterate(node)(_.next).takeWhile(_ != null).map(_.x).toList

def plusOne(head: ListNode): ListNode = {
  val l0 = toList(head)
  val l1 = List(1)
  val res = l0.reverse.zipAll(l1, 0, 0).foldLeft((List.empty[Int], 0)){
    case ((acc, c), (x0, x1)) =>
      val s = x0 + x1 + c
      if (s >= 10) (s-10 :: acc, 1) else (s :: acc, 0)
  }
  toNode(if (res._2 == 0) res._1 else 1 :: res._1)
}

Note that rather than converting ListNode elements to numbers that might be problematic for large ListNodes, fold is used to perform iterative element-wise summation.

Testing the code:

toList( plusOne( toNode(List(0)) ) )
// res0: List[Int] = List(1)

toList( plusOne( toNode(List(1, 2, 3)) ) )
// res1: List[Int] = List(1, 2, 4)

toList( plusOne( toNode(List(2, 9, 9)) ) )
// res2: List[Int] = List(3, 0, 0)

toList( plusOne( toNode(List(9, 9, 9)) ) )
// res3: List[Int] = List(1, 0, 0, 0)
user_63165080

Not very efficient solution, but for sure the shortest:

(List(1,2,3).mkString.toInt + 1).toString.toList.map(_.asDigit)

Code run at Scastie

In Scala 2.13 you can use List.unfold:

def increaseLast(list: List[Int]): List[Int] = List.unfold(list) {
  case Nil =>
    None
  case x :: Nil =>
    Some((x + 1) % 10, Nil)
  case x :: xs if xs.forall(_ == 9) =>
    Some((x + 1) % 10, xs)
  case x :: xs =>
    Some(x, xs)
}

Code run at Scastie.

user_23592270
Related