题解 | #链表相加(二)#

链表相加(二)

https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

#include <stack>
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if (head1==nullptr) {
        return head2;
        }
        if (head2==nullptr) {
        return head1;
        }
        stack<int> st1,st2;    //利用堆栈将各自数字入栈,再pop相加
        ListNode *p1 = head1, *p2 = head2;
        while (p1!=nullptr) {
        st1.push(p1->val);
        p1=p1->next;
        }
        while (p2!=nullptr) {
        st2.push(p2->val);
        p2=p2->next;
        }
        int add=0; auto dump=new ListNode(-1);   //利用add标记是否进位
        dump->next=nullptr;
        while (!st1.empty()||!st2.empty()) {
            int v1=0,v2=0;
            if (!st1.empty()) {
            v1=st1.top();
            st1.pop();   
            }
            if (!st2.empty()) {
            v2=st2.top();
            st2.pop();   
            }
            int sum=v1+v2+add;
            add=0;
            if (sum>9) {
                sum=sum%10;
                add=1;
            }
            auto temp=new ListNode(sum); //将每次相加后的节点头插法插入新链表
            temp->next=dump->next;
            dump->next=temp;
        }
        if (add==1) {    //若最后为1代表最高位需要进位,则在头部插入进位节点1
        auto temp=new ListNode(add);
        temp->next=dump->next;
        dump->next=temp;
        }
        return dump->next;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:25
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务