数据结构之两数相加(链表) | 春日游, 杏花吹满头

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

分辨遍历两个链表, 对应位置上的数字相加, 大于10的求余作为当前相加的值, 并且进一位，下一个位置上的相加后再加上进的位数, 如果最后位置上的相加大于10, 则在链表上补上进的位数, 举例: (2 -> 4 -> 3) + (4 -> 6 -> 9), 2 + 4 = 6, 4 + 6 = 10因为10 % 10 = 0, 所以该位置上的值为0, 同时向上进一位10 / 10 = 1, 此时值为[6, 0, …], 继续向下3 + 9 + 1 = 13, 1为进的数, 13 % 10 = 3, 此时该位置上值为3, 由于最后一位大于10, 所以链表上需要补上13 / 10 = 1, 最后的值为[6, 0, 3, 1]

代码

Python3

def twoNumSum(self, l1, l2):
  def dfs(l, r, i)
    if not l1 and not l2 and not i:
      return None

    // 对应位置上两数相加再加上大于10进的一位
    temp = (l1.val if l else 0) + (l2.val if r else 0) + i

    // 对应位置上的值
    node = ListNode(temp % 10)

    // 递归
    node.next = dfs(l.next if l else None, r.next if r else None, temp // 10)
    return node
  return dfs(l1, l2, 0)

JavaScript

function twoNumSum(l1, l2) {
  let head = null
  let tail = null
  let temp = 0

  while (l1 || l2) {
    // l1, l2每个位置上的值
    const n1 = l1 ? l1.val : 0
    const n2 = l2 ? l2.val : 0
    // l1, l2每个位置上的值相加再加上进的位数的值
    const sum = n1 + n2 + temp
    // 如果head不存在, 将head, tail指针指向取余的值
    if (!head) {
      head = tail = new ListNode(sum % 10)
    } else {
      tail.next = new ListNode(sum % 10)
      tail = tail.next
    }

    temp = Math.floor(sum / 10)
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  // 将tail指针指向temp
  if (temp > 0) {
    tail.next = new ListNode(temp)
  }
  return head
}