【MEDIUM】Add Two Numbers II

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

问题

You are given two linked lists representing two non-negative numbers. 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 Node {
public:
    int val;
    Node *next;
    
    Node(int val) {
        this->val = val;
        this->next = nullptr;
    }
    
    Node *copy() {
        return new Node(val);
    }
};

std::vector<Node *> stackForNum(Node *num) {
    std::vector<Node *> stack;
    Node *tmp = num;
    while (tmp) {
        stack.push_back(tmp);
        tmp = tmp->next;
    }
    return stack;
}

Node *addNode(Node *n1, Node *n2, int carry, int *carryOut) {
    int sum = carry;
    // nullptr的节点不会被相加
    if (n1) {
        sum += n1->val;
    }
    if (n2) {
        sum += n2->val;
    }
    *carryOut = sum / 10;
    return new Node(sum % 10);
}

Node *addList(Node *num1, Node *num2) {
    // 使用栈反转链表
    std::vector<Node *> numStack1 = stackForNum(num1);
    // 使用栈反转链表
    std::vector<Node *> numStack2 = stackForNum(num2);
    // 结果栈
    std::vector<Node *> resultStack;
    // 进位
    int carry = 0;
    while (!(numStack1.empty() && numStack2.empty())) {
        // 节点相加,如果栈到末尾了,用 nullptr
        Node *n1 = numStack1.empty() ? nullptr : ({
            Node *back = numStack1.back();
            numStack1.pop_back();
            back;
        });
        Node *n2 = numStack2.empty() ? nullptr : ({
            Node *back = numStack2.back();
            numStack2.pop_back();
            back;
        });
        Node *r = addNode(n1, n2, carry, &carry);
        resultStack.push_back(r);
    }
    
    if (resultStack.empty()) {
        // 如果结果是空栈,返回 0
        return new Node(0);
    } else {
        // 最后处理进位
        resultStack.back()->val += carry;
        if (resultStack.back()->val == 0) {
            resultStack.push_back(new Node(1));
        }
        // 最后将结果栈反转得到最终链表
        Node resultRoot = Node(0);
        Node *tmp = &resultRoot;
        while (!resultStack.empty()) {
            tmp->next = resultStack.back();
            resultStack.pop_back();
            tmp = tmp->next;
        }
        return resultRoot.next;
    }
}

int main(int argc, const char * argv[]) {
    
    Node *num1 = ({
        Node *n1 = new Node(7);
        Node *n2 = new Node(2);
        Node *n3 = new Node(4);
        Node *n4 = new Node(3);
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;
        n1;
    });
    
    Node *num2 = ({
        Node *n1 = new Node(5);
        Node *n2 = new Node(6);
        Node *n3 = new Node(4);
        n1->next = n2;
        n2->next = n3;
        n1;
    });
    
    
    Node *result = addList(num1, num2);
    
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕