algorithm - Scala 中链表链的尾递归解决方案

Question

我想为 Leetcode 上的以下问题写一个尾递归解决方案 -
给定两个表示两个非负整数的非空链表。数字以相反的顺序存储，它们的每个节点都包含一个数字。将两个数字相加并将其作为链表返回。
您可以假设这两个数字不包含任何前导零，除了数字 0 本身。
例子:

*Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)*
*Output: 7 -> 0 -> 8*
*Explanation: 342 + 465 = 807.*

Link to the problem on Leetcode
我无法找到在最后一行中调用递归函数的方法。
我在这里试图实现的是递归调用 add 函数，该函数将两个列表的头部与进位相加并返回一个节点。返回的节点与调用堆栈中的节点链接在一起。
我对 Scala 很陌生，我猜我可能错过了一些有用的构造。

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
import scala.annotation.tailrec
object Solution {
  def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
    add(l1, l2, 0)
  }
  //@tailrec
  def add(l1: ListNode, l2: ListNode, carry: Int): ListNode = {
    var sum = 0;
    sum = (if(l1!=null) l1.x else 0) + (if(l2!=null) l2.x else 0) + carry;
    if(l1 != null || l2 != null || sum > 0)
      ListNode(sum%10,add(if(l1!=null) l1.next else null, if(l2!=null) l2.next else null,sum/10))
    else null;
  }
}

Answer 1

你有几个问题，这些问题大多可以减少，因为它不是惯用的。
诸如 var 之类的东西和 null不常见 斯卡拉 通常，您会使用尾递归算法来避免此类事情。
最后，请记住尾递归算法要求最后一个表达式是普通值或递归调用。为此，您通常会跟踪剩余的工作以及累加器。
这是一个可能的解决方案:

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

def sum(n1: Number, n2: Number): Number = {
  def aux(d1: Digit, d2: Digit, carry: Digit): (Digit, Digit) = {
    val tmp = d1 + d2 + carry
    val d = tmp % 10
    val c = tmp / 10
    
    d -> c
  }

  @annotation.tailrec
  def loop(r1: Number, r2: Number, acc: Number, carry: Digit): Number =
    (r1, r2) match {
      case (d1 :: tail1, d2 :: tail2) =>
        val (d, c) = aux(d1, d2, carry)
        loop(r1 = tail1, r2 = tail2, d :: acc, carry = c)

      case (Nil, d2 :: tail2) =>
        val (d, c) = aux(d1 = 0, d2, carry)
        loop(r1 = Nil, r2 = tail2, d :: acc, carry = c)

      case (d1 :: tail1, Nil) =>
        val (d, c) = aux(d1, d2 = 0, carry)
        loop(r1 = tail1, r2 = Nil, d :: acc, carry = c)

      case (Nil, Nil) =>
        acc
    }

  loop(r1 = n1, r2 = n2, acc = List.empty, carry = 0).reverse
}

现在，这种递归往往非常冗长。
通常，stdlib 提供了使相同算法更简洁的方法:

// This is a solution that do not require the numbers to be already reversed and the output is also in the correct order.
def sum(n1: Number, n2: Number): Number = {
  val (result, carry) = n1.reverseIterator.zipAll(n2.reverseIterator, 0, 0).foldLeft(List.empty[Digit] -> 0) {
    case ((acc, carry), (d1, d2)) =>
      val tmp = d1 + d2 + carry
      val d = tmp % 10
      val c = tmp / 10
      (d :: acc) -> c
  }


  if (carry > 0) carry :: result else result
}