(129)445. 两数相加 II(leetcode)

    科技2024-11-09  13

    题目链接: https://leetcode-cn.com/problems/add-two-numbers-ii/ 难度:中等 445. 两数相加 II 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。 将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外,这两个数字都不会以零开头。 进阶: 如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。 示例: 输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 8 -> 0 -> 7

    还行 不算难 用栈把链表中的值全部存进去就行了 逆序嘛 栈还是很合适的

    /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1->val==0){ return l2; } if(l2->val==0){ return l1; } stack<int> sta1,sta2; while(l1!=nullptr){ sta1.push(l1->val); l1=l1->next; } while(l2!=nullptr){ sta2.push(l2->val); l2=l2->next; } int c=0; ListNode* ans=nullptr; while(!sta1.empty()||!sta2.empty()){ int a=0,b=0; if(!sta1.empty()){ a=sta1.top(); sta1.pop(); } if(!sta2.empty()){ b=sta2.top(); sta2.pop(); } int sum=a+b+c; c=sum/10; auto cur=new ListNode(sum%10); cur->next=ans; ans=cur; } if(c){ auto cur=new ListNode(c); cur->next=ans; ans=cur; } return ans; } };
    Processed: 0.045, SQL: 8