2.两数相加

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例:
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

题解

双指针 O(max(m,n)) O(1)

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null,
): ListNode | null {
  let p1 = l1
  let p2 = l2
  let res = new ListNode(-1)
  let prevNode = res
  let carry = 0
  while (p1 || p2 || carry > 0) {
    const plus = (p1?.val || 0) + (p2?.val || 0) + carry
    const curVal = plus % 10
    carry = Math.floor(plus / 10)
    const curNode = new ListNode(curVal)
    prevNode.next = curNode
    prevNode = curNode
    p1 = p1?.next
    p2 = p2?.next
  }
  return res.next
}

const l1 = new LinkedList([2, 4, 3]),
  l2 = new LinkedList([5, 6, 4])
console.log('🌰', addTwoNumbers(l1.head, l2.head))

const l3 = new LinkedList([9, 9, 9, 9, 9, 9, 9]),
  l4 = new LinkedList([9, 9, 9, 9])
console.log('🌰', addTwoNumbers(l3.head, l4.head))

2.两数相加 ​

题目 ​

题解 ​

2.两数相加

题目

题解