力扣-445题两数相加II（C++）

梦里梦外; 2023-01-24 02:05 193阅读 0赞

题目链接：[https://leetcode-cn.com/problems/add-two-numbers-ii/][https_leetcode-cn.com_problems_add-two-numbers-ii]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
注：不反转链表，则新建两个栈，把各个链表中的元素放入对应的栈中，然后pop出来，这种思路是空间换取时间。而反转链表的思路是时间换取空间。

/**
     * 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* reverse(ListNode* head){
        //反转链表
            if(head==NULL||head->next==NULL) return head;//没有或只有一个节点，直接返回
            ListNode* a=head;
            ListNode* b=head->next;
    
            while(b!=NULL){
        //留意，第一次调试，这里语句错误，还需熟练
                ListNode* c=b->next;
                b->next=a;
                a=b;b=c;
            }
            head->next=NULL;
    
            return a;
        }
    
        void print(ListNode* head){
        //仅作测试使用
            while(head!=NULL){
        
                cout<<head->val<<' ';
                head=head->next;
            }
        }
    
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
            //tip：
            //1、两个链表进行相加，考虑三种情况：l1未空，l2未空和进位未空
            //2、反转链表中的出错语句再多留意
            //3、进位的英文为carry
            
            l1=reverse(l1);
            l2=reverse(l2);
            print(l1);
    
            ListNode* result=NULL;
            int carry=0;
    
            while(l1!=NULL&&l2!=NULL){
        
    
                auto node=new ListNode((l1->val+l2->val+carry)%10);
                carry=(l1->val+l2->val+carry)/10;
    
                node->next=result;//每次在链表最前端插入节点
                result=node;
    
                l1=l1->next;l2=l2->next;
            }
    
            while(l1!=NULL){
        //l1还未结束
                auto node=new ListNode((l1->val+carry)%10);
                carry=(l1->val+carry)/10;
    
                node->next=result;//每次在链表最前端插入节点
                result=node;
    
                l1=l1->next;
            }
    
            while(l2!=NULL){
        //l2还未结束
                auto node=new ListNode((l2->val+carry)%10);
                carry=(l2->val+carry)/10;
    
                node->next=result;//每次在链表最前端插入节点
                result=node;
    
                l2=l2->next;
            }
    
            if(carry!=0){
        //进位还未加入
                auto node=new ListNode(carry);
    
                node->next=result;//每次在链表最前端插入节点
                result=node;
            }
    
            return result;
        }
    };

[https_leetcode-cn.com_problems_add-two-numbers-ii]: https://leetcode-cn.com/problems/add-two-numbers-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221004/f73c7cc400b74aa58faf70611078f62d.png