数据结构之链表两数相加

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

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

您可以假设除了数字 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 l and not not r and not i: return None
    // 对应位置上的数值相加再加上大于10时进的一位
    temp = (l.val if l else 0) + (r.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) {
    // n1, n2对应位置上的值
    let n1 = l1 ? l1.val : 0
    let n2 = l2 ? l2.val : 0
    // 对应位置上的值相加再加上大于10时进的一位
    let 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
}