题解 | #两个链表生成相加链表#

两个链表生成相加链表

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

//三次反转列表即可
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        //将链表反转
        auto new_head1 = new ListNode(-1);
        ListNode *next;
        while(head1){
            next = head1->next;
            head1->next = new_head1->next;
            new_head1->next = head1;
            head1 = next;
        }
        head1 = new_head1->next;//链表1反转结束
        new_head1->next = nullptr;
        while(head2){
            next = head2->next;
            head2->next = new_head1->next;
            new_head1->next = head2;
            head2 = next;
        }
        head2 = new_head1->next;//链表2反转结束
        int carry = 0;
        auto left = head1,right = head2;
        ListNode *prev = nullptr;
        while(left && right){
            int res = left->val + right->val + carry;
            if(res >= 10){
                carry = 1;
                left->val = res - 10;
            }else{
                carry = 0;
                left->val = res;
            }
            prev = left;
            left = left->next;
            right = right->next;
        }
        while(left){
            int res = left->val + carry;
            if(res >= 10){
                carry = 1;
                left->val = res - 10;
            }else{
                carry = 0;
                left->val = res;
                break;
            }
            prev = left;
            left = left->next;
        }
        if(carry == 1)
            prev->next = new ListNode(1);
        if(right)prev->next = right;
        while(right){
            int res = right->val + carry;
            if(res >= 10){
                carry = 1;
                right->val = res - 10;
            }else{
                carry = 0;
                right->val = res;
                break;
            }
            prev = right;
            right = right->next;
        }
        if(carry == 1)
            prev->next = new ListNode(1);
        //再翻转下
        new_head1->next = nullptr;
        while(head1){
            next = head1->next;
            head1->next = new_head1->next;
            new_head1->next = head1;
            head1 = next;
        }
        return new_head1->next;
    }
};
全部评论

相关推荐

当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
头像
05-16 11:16
已编辑
东华理工大学 Java
牛客737698141号:盲猜几十人小公司,庙小妖风大,咋不叫她去4️⃣呢😁
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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