1. 题目
  2. 解题思路

2 Add Two Numbers

leetcode algorithm

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order 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.

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

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

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

1
2
3
4
5
Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

将两个链表的值相加, 然后判断是否需要进位(>=10), 如果需要进位,就在计算下一组数值时 +1.

特殊情况:
1 链表长度不等: [5, 6, 7], [3]
2 链表最后一位需要进位: [5], [5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function ListNode(val) {
  this.val = val;
  this.next = null;
}
const addTwoNumbers = function(l1, l2) {
  let carry = 0;
  const head = new ListNode(0);
  let node = head;
  while (l1 || l2) {
    let num = 0;
    // 进位
    if (carry === 1) {
      num = 1;
    }
    // 相加
    if (l1 !== null) {
      num += l1.val;
      l1 = l1.next;
    }
    if (l2  !== null) {
      num += l2.val;
      l2 = l2.next;
    }
    // 判断下一个数值是否需要进位
    if (num >= 10) {
      carry = 1;
      num = num - 10;
    } else {
      carry = 0;
    }
    node.next = new ListNode(num);
    node = node.next;
  }
  // 结束循环时,最后一位可能存在进位,例如: [5],[5]
  if (carry) {
    node.next = new ListNode(1);
  }
  return head.next;
};

// test
const l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);
const l2 = new ListNode(5);
l2.next = new ListNode(6);
l2.next.next = new ListNode(4);

console.log(addTwoNumbers(l1, l2));