Task

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.

Example

1
2
3

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

Solution

  • 本题用链表来模拟进位，进行高精度加法的计算 leetcode2
  • 上图中提供了dummy head的链表进行模拟加法的代码
  • 遍历时两个指针在两个链表中同时推进，当两个指针都为空（两个链表都走完）且进位值为0时结束循环
  • 指针每推进一步，就对两链表中元素求和sum，并在储存结果的新链表中增加一个节点，该节点值为sum%10，进位值为sum/10
  • 时间复杂度：只遍历一次，取决于较长的链表，故O(max{m,n})
  • 空间复杂度：新建的链表长度也取决于较长的链表，故O(max{m,n})
  • 实现：
 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

// Runtime: 24 ms, faster than 94.84% of C++ online submissions for Add Two Numbers.
// Memory Usage: 70.2 MB, less than 5.14% of C++ online submissions for Add Two Numbers.
/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //新建链表的节点，该指针用于从链表中返回值
        auto dummy=new ListNode;
        //用另一个指针指向新链表，该指针用于在链表中遍历
        ListNode *tail=dummy;
        int sum=0,carry=0;
        //当两个链表都走完且无进位时终止循环
        while(l1||l2||carry){
            //对该位求和，考虑上一位的进位
            //若l1/l2的当前指针非空，则值存在，加上该值。若不存在说明已走完该链表
            sum=(l1?l1->val:0)+(l2?l2->val:0)+carry;
            //若l1/l2的当前指针非空，则继续走
            l1=l1?l1->next:nullptr;
            l2=l2?l2->next:nullptr;
            //向新链表中新建节点，存储结果中该位的值，考虑进位
            tail->next=new ListNode(sum%10);
            //新链表指针移动
            tail=tail->next;
            //计算进位
            carry=sum/10;
        }
        return dummy->next;
    }
};