scala - 加一链表: Functional Approach

Question

我一直在为这个 leetcode 问题绞尽脑汁。想知道是否有一种实用的方法可以解决这个问题。我能想到的就是使用可变对象(在 Scala 中)。

给定一个表示为数字链接列表的非负整数，该整数加一。

存储数字时，最高有效数字位于列表的开头。

示例1:

输入:head = [1,2,3] 输出:[1,2,4]

示例2:

输入:head = [0] 输出:[1]

限制:

链表中的节点数量在[1, 100]范围内。

0 <= Node.val <= 9

链表表示的数字除了零本身之外不包含前导零。

 * 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 = {
        
    }
}

更有趣的输入/输出 = [1,9,9,9,9] => [2,0,0,0,0]

Answer 1

(tail)递归来救援!

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)
}

你可以这样使用:

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

---

您可以看到代码正在运行 here .