leetcode-445. 两数相加 II

男娘i 2022-10-24 11:53 147阅读 0赞

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)  
输出：7 -> 8 -> 0 -> 7

来源：力扣（LeetCode）  
链接：[leetcode-445. 两数相加 II][leetcode-445. _ II]

思路：  
1.将链表的数据放到vector数组中（按照链表的顺序）  
2.将vector中的数据从后向前一位一位相加，进位  
3.并将相加得到的数，放到新的链表中去

代码：

class Solution {
        
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
            vector<int>s1;
            vector<int>s2;
    
            while(l1!=nullptr)
            {
        
                s1.push_back(l1->val);
                l1=l1->next;
            }
            while(l2!=nullptr)
            {
        
                s2.push_back(l2->val);
                l2=l2->next;
            }
        int carry=0;
        ListNode* ret=nullptr;
    
            while(s1.size()>0||s2.size()>0||carry>0)
            {
        
                int sum=carry;
    
                if(s1.size()>0)
                {
        
                    int  item=s1.back();
                    s1.pop_back();
                    sum=sum+item;
                }
                if(s2.size()>0)
                {
        
                    int item=s2.back();
                    s2.pop_back();
                    sum=sum+item;
                }
                ListNode* temp=new ListNode(sum%10);
                carry=sum/10;
    
                temp->next=ret;
                ret=temp;
    
    
            }
    
    
            return ret;
    
    
        }
    };

[leetcode-445. _ II]: https://leetcode-cn.com/problems/add-two-numbers-ii