【MEDIUM】Add Two Numbers II

发布于: 2018-12-25 18:06
阅读: 71
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/add-two-numbers-ii/

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

  • What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

分析过程

  • 输入:两个含单位数字的链表
  • 输出:相加以后的结果链表
  • 思路:其实是个大数加法。Follow up 中不允许反转链表,那么可以用栈来处理,元素全部压栈,从后面弹栈来相加。需要注意的是长度不一样的两个数,栈的深度不一样,需要特殊处理。另外最后的进位也需要单独处理。

解决方法

class Solution {
public:
    std::vector<ListNode *> stackForNum(ListNode *num) {
        std::vector<ListNode *> stack;
        ListNode *tmp = num;
        while (tmp) {
            stack.push_back(tmp);
            tmp = tmp->next;
        }
        return stack;
    }
    
    ListNode *addNode(ListNode *n1, ListNode *n2, int carry, int *carryOut) {
        int sum = carry;
        // nullptr的节点不会被相加
        if (n1) {
            sum += n1->val;
        }
        if (n2) {
            sum += n2->val;
        }
        *carryOut = sum / 10;
        return new ListNode(sum % 10);
    }
    
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 使用栈反转链表
        std::vector<ListNode *> numStack1 = stackForNum(l1);
        // 使用栈反转链表
        std::vector<ListNode *> numStack2 = stackForNum(l2);
        // 结果栈
        std::vector<ListNode *> resultStack;
        // 进位
        int carry = 0;
        while (!(numStack1.empty() && numStack2.empty())) {
            // 节点相加,如果栈到末尾了,用 nullptr
            ListNode *n1 = numStack1.empty() ? nullptr : ({
                ListNode *back = numStack1.back();
                numStack1.pop_back();
                back;
            });
            ListNode *n2 = numStack2.empty() ? nullptr : ({
                ListNode *back = numStack2.back();
                numStack2.pop_back();
                back;
            });
            ListNode *r = addNode(n1, n2, carry, &carry);
            resultStack.push_back(r);
        }
        
        // 最后处理进位
        if (carry) {
            resultStack.push_back(new ListNode(1));
        }
        
        if (resultStack.empty()) {
            // 如果结果是空栈,返回 0
            return new ListNode(0);
        } else {
            // 最后将结果栈反转得到最终链表
            ListNode resultRoot = ListNode(0);
            ListNode *tmp = &resultRoot;
            while (!resultStack.empty()) {
                tmp->next = resultStack.back();
                resultStack.pop_back();
                tmp = tmp->next;
            }
            return resultRoot.next;
        }
    }
};

Thanks for reading.

All the best wishes for you! 💕