[LeetCode] Add Two Numbers II 两个数字相加之二

简介:

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

这道题是之前那道Add Two Numbers的拓展,我们可以看到这道题的最高位在链表首位置,如果我们给链表翻转一下的话就跟之前的题目一样了,这里我们来看一些不修改链表顺序的方法。由于加法需要从最低位开始运算,而最低位在链表末尾,链表只能从前往后遍历,没法取到前面的元素,那怎么办呢?我们可以利用栈来保存所有的元素,然后利用栈的后进先出的特点就可以从后往前取数字了,我们首先遍历两个链表,将所有数字分别压入两个栈s1和s2中,我们建立一个值为0的res节点,然后开始循环,如果栈不为空,则将栈顶数字加入sum中,然后将res节点值赋为sum%10,然后新建一个进位节点head,赋值为sum/10,如果没有进位,那么就是0,然后我们head后面连上res,将res指向head,这样循环退出后,我们只要看res的值是否为0,为0返回res->next,不为0则返回res即可,参见代码如下:

解法一:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int sum = 0;
        ListNode *res = new ListNode(0);
        while (!s1.empty() || !s2.empty()) {
            if (!s1.empty()) {sum += s1.top(); s1.pop();}
            if (!s2.empty()) {sum += s2.top(); s2.pop();}
            res->val = sum % 10;
            ListNode *head = new ListNode(sum / 10);
            head->next = res;
            res = head;
            sum /= 10;
        }
        return res->val == 0 ? res->next : res;
    }
};

下面这种方法使用递归来实现的,我们知道递归其实也是用栈来保存每一个状态,那么也就可以实现从后往前取数字,我们首先统计出两个链表长度,然后根据长度来调用递归函数,需要传一个参数差值,递归函数参数中的l1链表长度长于l2,在递归函数中,我们建立一个节点res,如果差值不为0,节点值为l1的值,如果为0,那么就是l1和l2的和,然后在根据差值分别调用递归函数求出节点post,然后要处理进位,如果post的值大于9,那么对10取余,且res的值自增1,然后把pos连到res后面,返回res,最后回到原函数中,我们仍要处理进位情况,参见代码如下:

解法二:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int n1 = getLength(l1), n2 = getLength(l2);
        ListNode *head = new ListNode(1);
        head->next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1);
        if (head->next->val > 9) {
            head->next->val %= 10;
            return head;
        }
        return head->next;
    }
    int getLength(ListNode* head) {
        int cnt = 0;
        while (head) {
            ++cnt;
            head = head->next;
        }
        return cnt;
    }
    ListNode* helper(ListNode* l1, ListNode* l2, int diff) {
        if (!l1) return NULL;
        ListNode *res = (diff == 0) ? new ListNode(l1->val + l2->val) : new ListNode(l1->val);
        ListNode *post = (diff == 0) ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1);
        if (post && post->val > 9) {
            post->val %= 10;
            ++res->val;
        }
        res->next = post;
        return res;
    }
};

下面这种方法借鉴了Plus One Linked List中的解法三,在处理加1问题时,我们需要找出右起第一个不等于9的位置,然后此位置值自增1,之后的全部赋为0。这里我们同样要先算出两个链表的长度,我们把其中较长的放在l1,然后我们算出两个链表长度差diff。如果diff大于0,我们用l1的值新建节点,并连在cur节点后(cur节点初始化时指向dummy节点)。并且如果l1的值不等于9,那么right节点也指向这个新建的节点,然后cur和l1都分别后移一位,diff自减1。当diff为0后,我们循环遍历,将此时l1和l2的值加起来放入变量val中,如果val大于9,那么val对10取余,right节点自增1,将right后面节点全赋值为0。在cur节点后新建节点,节点值为更新后的val,如果val的值不等于9,那么right节点也指向这个新建的节点,然后cur,l1和l2都分别后移一位。最后我们看dummy节点值若为1,返回dummy节点,如果是0,则返回dummy的下一个节点。

解法三:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int n1 = getLength(l1), n2 = getLength(l2), diff = abs(n1 - n2);
        if (n1 < n2) swap(l1, l2);
        ListNode *dummy = new ListNode(0), *cur = dummy, *right = cur;
        while (diff > 0) {
            cur->next = new ListNode(l1->val);
            if (l1->val != 9) right = cur->next;
            cur = cur->next;
            l1 = l1->next;
            --diff;
        }
        while (l1) {
            int val = l1->val + l2->val;
            if (val > 9) {
                val %= 10;
                ++right->val;
                while (right->next) {
                    right->next->val = 0;
                    right = right->next;
                }
                right = cur;
            }
            cur->next = new ListNode(val);
            if (val != 9) right = cur->next;
            cur = cur->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        return (dummy->val == 1) ? dummy : dummy->next;
    }
    int getLength(ListNode* head) {
        int cnt = 0;
        while (head) {
            ++cnt;
            head = head->next;
        }
        return cnt;
    }
};

本文转自博客园Grandyang的博客,原文链接:两个数字相加之二[LeetCode] Add Two Numbers II ,如需转载请自行联系原博主。

相关文章
|
10月前
|
存储 缓存 算法
LeetCode刷题---Two Sum(一)
LeetCode刷题---Two Sum(一)
|
8月前
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
19 0
|
8月前
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
32 0
|
10月前
|
存储 C++ Python
LeetCode刷题---Add Two Numbers(一)
LeetCode刷题---Add Two Numbers(一)
|
存储 算法 安全
LeetCode - #2 Add Two Numbers
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #2 Add Two Numbers
|
存储 算法 安全
LeetCode - #1 Two Sum
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。
LeetCode - #1 Two Sum
LeetCode 167 Two Sum II - Input array is sorted(输入已排序数组,求其中两个数的和等于给定的数)
给定一个有序数组和一个目标值 找出数组中两个成员,两者之和为目标值,并顺序输出
70 0
|
存储 前端开发 算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
120 0
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
LeetCode 21. 合并两个有序链表 Merge Two Sorted Lists
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
122 0