PigyChan_LeetCode 445. 两数相加 II-白红宇

PigyChan_LeetCode 445. 两数相加 II

阅读量：3945 次

发布时间：2019-05-24

本文共 1859 字，大约阅读时间需要 6 分钟。

445. 两数相加 II

难度中等

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 8 -> 0 -> 7

在我看来这题的难点在于进位

思路1.0：

（1）遍历两条链表，得到两链表长度，big，small分别存储较长边和较短边

（2）以较长链表为基构造ans链表，该链表以一个值为0的节点为头，为进位提供空间
（3）将较短链表加入ans
（4）。。。意识到要使用stack，那为啥不在一开始就用呢。。

思路2.0：

（1）遍历两条链表，将两链表压入两个栈。

（2）最后通过两个栈一起弹出元素，模拟两数从个位开始相加，记录进位，并将最终和作为val来构造ans链表。

代码1.0：

class Solution {
   public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
           ListNode* cur1 = l1;        ListNode* cur2 = l2;        stack
   
     stk1;        stack
    
      stk2;        while (cur1 != NULL) {
               stk1.push(cur1->val);            cur1 = cur1->next;        }        while (cur2 != NULL) {
               stk2.push(cur2->val);            cur2 = cur2->next;        }        ListNode* after = NULL;        bool isCarry = false;        while (!stk1.empty() || !stk2.empty()) {
               int val1 = 0;            int val2 = 0;            if (!stk1.empty()) {
                   val1 = stk1.top();                stk1.pop();            }            if (!stk2.empty()) {
                   val2 = stk2.top();                stk2.pop();            }                        int newVal = val1 + val2 + isCarry;            //存在进位            if (newVal >= 10) {
                   newVal = newVal % 10;                isCarry = true;            }            //没有进位            else {
                   isCarry = false;            }            ListNode* newNode = new ListNode(newVal);            newNode->next = after;            after = newNode;        }        if (isCarry) {
               ListNode* newNode = new ListNode(1);            newNode->next = after;            after = newNode;        }        return after;    }};

以后看到两数相加要第一时间想到栈

效率还是不咋地，去题解逛逛

转载地址：http://bvowi.baihongyu.com/

你可能感兴趣的文章