Add Two Numbers

题目:

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.

来源:LeetCode

例子:

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

算法:

  1. 初始化返回的 NodeList 的头结点
  2. 初始化进位carry为 0
  3. 将列表 l1l2 头结点赋值给 pq
  4. p 或者 q 存在遍历列表 l1l2
    1. p 的值赋值给 xq 的值赋值给 ypq不存在,则赋值为0
    2. 计算sum = x + y + carry
    3. carry = sum / 10
    4. 创建一个新的节点newNode: newNode.val = sum % 10,并将当前节点的next指向这个节点newNode
    5. 当前节点进一位,即: cur = cur.next
    6. 如果p存在,将p.next赋值给p
    7. 如果q存在,将q.next赋值给q
  5. 如果进位为1,则增加一个新的节点,节点值为 1
  6. 返回头结点的next

算法复杂度

  • 时间复杂度:O(max(m, n)) l1l2的最大长度即遍历的迭代次数。
  • 空间复杂度:O(max(m, n)) 返回的新的list 最大长度是 max(m, n) + 1

code:

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const addTwoNumbers = function(l1, l2) {
const dummyHead = new ListNode();
let carry = 0;
let sum = 0;
let p = l1;
let q = l2;
let cur = dummyHead;
while(p || q) {
const x = p ? p.val : 0;
const y = q ? q.val : 0;
sum = x + y + carry;
carry = Math.floor(sum / 10);
const newNode = new ListNode(sum % 10);
cur.next = newNode;
cur = cur.next;
if(p) {
p = p.next;
}
if(q) {
q = q.next;
}
}
if(carry === 1) {
cur.next = new ListNode(1);
}

return dummyHead.next;
};