两数相加（leetcode 2）

1.问题描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
1
2

示例 2：

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

示例 3：

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

2.难度等级

medium。

3.热门指数

★★★★☆

出题公司：微派网络。

4.解题思路

思路其实在示例中已经描述的非常清楚了，难度主要是编码实现。

遍历两个链表，将节点值相加，并与当前位置的进位值相加。如果产生进位，则将进位带到下一对节点。

具体而言，如果当前两个链表处相应位置的数字为 n1 和 n2，结果为 (n1+n2) mod 10，进位为 (n1+n2) / 10。

注意一点，如果两个链表最后一个节点产生了进位，需要生成新的节点。

复杂度分析：

• 时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
• 空间复杂度：O(1)。注意返回值不计入空间复杂度。

5.实现示例

5.1 C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

// addTwoNumbers 两数相加。
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
  ListNode *head = nullptr, *cur = nullptr;
  int carry = 0;
  while (l1 || l2) {
    int n1 = 0, n2 = 0;
    if (l1) {
      n1 = l1->val;
      l1 = l1->next;
    }
    if (l2) {
      n2 = l2->val;
      l2 = l2->next;
    }
    // 节点值相加。
    int sum = n1 + n2 + carry;
    carry = sum / 10;
    sum = sum % 10;
    if (!head) {
      head = cur = new ListNode(sum);
    } else {
      cur->next = new ListNode(sum);
      cur = cur->next;
    }
  }
  // 如果最后一个节点产生了进位，需要生成新的节点。
  if (carry > 0) {
    cur->next = new ListNode(carry);
  }
  return head;
}
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

5.2 Golang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// addTwoNumbers 两数相加。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var head, cur *ListNode
    var carry int
    for l1 != nil || l2 != nil {
      	n1, n2 := 0, 0
        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
		// 节点值相加。
		sum := n1 + n2 + carry
        sum, carry = sum%10, sum/10
        if head == nil {
            head = &ListNode{Val: sum}
            cur = head
        } else {
            cur.Next = &ListNode{Val: sum}
            cur = cur.Next
        }
    }
    // 如果最后一个节点产生了进位，需要生成新的节点。
    if carry > 0 {
        cur.Next = &ListNode {
            Val:carry,
        }
    }
    return head
}
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

---

参考文献

2. 两数相加 - LeetCode