leeecode 445. Add Two Numbers II 链表相加

悠悠 2022-06-04 08:24 161阅读 0赞

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

题意很简单，做法如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    
    using namespace std;
    
    
    /*
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
        {
            vector<int> nums1, nums2;
            while (l1) 
            {
                nums1.push_back(l1->val);
                l1 = l1->next;
            }
            while (l2) 
            {
                nums2.push_back(l2->val);
                l2 = l2->next;
            }
    
            int m = nums1.size(), n = nums2.size();
            int sum = 0, carry = 0;
    
            ListNode *head = nullptr, *p = nullptr;
    
            for (int i = m - 1, j = n - 1; i >= 0 || j >= 0 || carry > 0; i--, j--)
            {
                sum = carry;
                if (i >= 0)
                    sum += nums1[i];
                if (j >= 0)
                    sum += nums2[j];
                carry = sum / 10;
    
                p = new ListNode(sum % 10);
                p->next = head;
                head = p;
            }
    
            return head;
        }
    };