Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Analyze

思考: 相对题 2 的逆序相加, 该题顺序相加作如下思考:

  • 第一步: 首先补齐位数, 让其一一对应;
7 -> 2 -> 4 -> 3
0 -> 5 -> 6 -> 4
  • 第二步: 递归计算两个链表同位之和, 同时使用 digitCarry 表示进位的情况;
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let countl1 = 0, countl2 = 0
let l1List = l1
let l2List = l2
while(l1List) {
countl1++
l1List = l1List.next
}
while(l2List) {
countl2++
l2List = l2List.next
}
// creat the frontest List
let tmpList = new ListNode(0)
let cur = tmpList
let diff = Math.abs(countl2 - countl1)
while (diff--) {
cur.next = new ListNode(0)
cur = cur.next
}
if (countl1 < countl2) {
cur.next = l1
l1 = tmpList.next
} else if (countl2 < countl1) {
cur.next = l2
l2 = tmpList.next
}
// flag: 1 shows digit carry, 0 not;
let digitCarry = 0
/**
* calculate the sum of l1 and l2
*/
function listNodeAdd(l1, l2) {
if (l1 === null) return
listNodeAdd(l1.next, l2.next)
let sum = l1.val + l2.val + digitCarry
if (sum >= 10) {
l1.val = sum % 10
digitCarry = 1
} else {
l1.val = sum
digitCarry = 0
}
}
listNodeAdd(l1, l2)
let result = l1
if (digitCarry === 1) {
result = new ListNode(1)
result.next = l1
}
return result
}

Sister Title

2