leetcode 445. Add Two Numbers II

淩亂°似流年 2022-06-13 06:11 138阅读 0赞

# 1.题目 #

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  
7243+564=7807

# 2.分析 #

一般来说，两个数的加法需要从最低位开始计算，然而单向链表只有向后的指针。  
两种方案  
1）用栈或者向量来存储每个链表的数字，达到可以从后往前访问的目的。 需要额外空间。  
2）从前往后计算，先按节点存储节点之和，然后计算进位。需要翻转结果链表。

# 3.代码 #

方案2

class Solution {
    public:
        ListNode* addNode(int value, ListNode* tail) {
            ListNode* tmp = new ListNode(value);
            tmp->next = tail;
            return tmp;
        }
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if (l1 == NULL)
                return l2;
            if (l2 == NULL)
                return l1;
            ListNode *list1 = l1, *list2 = l2, *ans = NULL;
            int len1 = 0, len2 = 0;
            while (list1) {
                list1 = list1->next;
                ++len1;
            }
            while (list2) {
                list2 = list2->next;
                ++len2;
            }
            list1 = l1;
            list2 = l2;
            while (len1 > len2) {
                ans = addNode(list1->val, ans);
                --len1;
                list1 = list1->next;
            }
            while (len2 > len1) {
                ans = addNode(list2->val, ans);
                --len2;
                list2 = list2->next;
            }
            while (list1&&list2) {
                ans = addNode(list1->val + list2->val, ans);
                list1 = list1->next;
                list2 = list2->next;
            }
            list1 = ans;
            ans = NULL;
            int carry = 0;
            while (list1) {
                list1->val += carry;
                carry = list1->val / 10;
                ans = addNode(list1->val%10, ans);
                list1 = list1->next;
            }
            if (carry)
                ans = addNode(1, ans);
            return ans;
        }
    };