LeetCode问题：链表表示整数加1的Scala函数式实现

嘿，我懂这种卡在链表题里想搞函数式解法的痛苦！不用可变对象完全可以搞定，咱们用递归+纯函数的思路来解决这个问题。

函数式编程的核心是避免可变状态，所以咱们不用var来跟踪进位，而是通过递归的返回值来传递「处理后的节点」和「当前进位」这两个信息。具体来说，我们可以写一个辅助递归函数，从链表末尾开始往前处理，每次返回更新后的节点和新的进位，最后再处理可能的最高位进位。

具体实现代码 #

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

object Solution {
  def plusOne(head: ListNode): ListNode = {
    // 辅助递归函数：输入当前节点，返回(处理后的节点, 进位值)
    def helper(node: ListNode): (ListNode, Int) = {
      node match {
        case null => (null, 1) // 递归到末尾，初始进位是1（因为要加1）
        case _ =>
          val (nextNode, carry) = helper(node.next)
          val total = node.x + carry
          val newVal = total % 10
          val newCarry = total / 10
          (new ListNode(newVal, nextNode), newCarry)
      }
    }

    val (resultNode, finalCarry) = helper(head)
    // 如果最后还有进位，说明需要在头部加一个1节点
    if (finalCarry == 1) new ListNode(1, resultNode) else resultNode
  }
}

思路拆解 #

• 递归辅助函数：helper函数负责递归遍历链表，每次先处理当前节点的下一个节点，拿到处理后的子链表和进位值。这样相当于从链表的最低位（末尾）开始计算，完美契合加1需要从低位到高位处理进位的逻辑。
• 进位传递：对于当前节点，把它的值加上子节点返回的进位，计算新的值和新的进位，然后创建一个新的节点（不修改原节点，符合函数式不可变的原则），并把处理后的子链表挂在它后面。
• 最终进位处理：如果递归完整个链表后，还有进位（比如输入是[9,9]，处理后会得到进位1），那就新建一个值为1的头节点，把结果链表挂在它后面；否则直接返回处理后的链表。

示例验证 #

咱们拿几个例子测试一下：

• 输入[1,2,3]：递归到末尾3，加1得4，进位0；回溯到2，加0还是2；再回溯到1，加0还是1，最终返回[1,2,4]。
• 输入[0]：递归到null返回进位1，0+1=1，进位0，最终返回[1]。
• 输入[1,9,9,9,9]：从最后一个9开始，加1得10，值0进位1；依次往前每个9加1都得10，值0进位1；直到第一个1加1得2，进位0；最终返回[2,0,0,0,0]。

这个实现完全没有用到可变变量，纯函数式风格，而且逻辑清晰，完美适配问题要求～

内容的提问来源于stack exchange，提问作者l33tHax0r