剑指 Offer II 025. 链表中的两数相加

剑指 Offer II 025. 链表中的两数相加

题目描述

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

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

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]

输出：[7,8,0,7]

思路一 反转链表

先将两个输入链表反转，然后就可以按照从前往后的顺序遍历进行相加计算。
需要注意的是需要记录一个进位数字。

那么主循环判断就是 两个链表其中一个不为空或者进位不为0，那么就需要一直计算当前位的数字，并构造链表。

常规思路是构造一个链表结点，然后继续向下走，再构造一个链表结点。

最后将得到的链表反转即可得到答案。

class Solution {
    ListNode* reverseList(ListNode* list){
        ListNode* ptr1 = nullptr;
        ListNode* ptr2 = list;

        while(ptr2 != nullptr){
            ListNode* temp = ptr2->next;        //记录ptr2 的下一个结点
            ptr2->next = ptr1;                  //反转链表
            ptr1 = ptr2;                        // 指针后移
            ptr2 = temp;
        }

        return ptr1;
    }

public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l1copy = reverseList(l1);
        ListNode* l2copy = reverseList(l2);

        int jw = 0;
        int num1 = 0, num2 = 0;
        ListNode* tmp = new ListNode(0);
        ListNode* ptr = tmp;
        while(l1copy != nullptr || l2copy != nullptr || jw){

            if(l1copy != nullptr){
                num1 = l1copy->val;
                l1copy = l1copy->next;
            }
            else{
                num1 = 0;
            }
            if(l2copy != nullptr){
                num2 = l2copy->val;
                l2copy = l2copy->next;
            }
            else{
                num2 = 0;
            }
            int num = num1 + num2 + jw;

            jw = num /10;
            num %= 10;

            ptr->next = new ListNode(num);
            ptr = ptr->next;
        }

        return reverseList(tmp->next);
    }
};

不过我们可以直接避免掉最后的链表反转，我们如果先给定一个链表结点指针p，最初指向 NULL，然后每次循环构造一个新的数字结点，该结点next为p，随后p指向该结点。

思考一下上述过程，是不是就可以有效避免掉最后的链表反转呢？

class Solution {
    ListNode* reverseList(ListNode* list){
        ListNode* ptr1 = nullptr;
        ListNode* ptr2 = list;

        while(ptr2 != nullptr){
            ListNode* temp = ptr2->next;        //记录ptr2 的下一个结点
            ptr2->next = ptr1;                  //反转链表
            ptr1 = ptr2;                        // 指针后移
            ptr2 = temp;
        }

        return ptr1;
    }

public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l1copy = reverseList(l1);
        ListNode* l2copy = reverseList(l2);

        int jw = 0;
        int num1 = 0, num2 = 0;
        ListNode* p = nullptr;
        while(l1copy != nullptr || l2copy != nullptr || jw){

            if(l1copy != nullptr){
                num1 = l1copy->val;
                l1copy = l1copy->next;
            }
            else{
                num1 = 0;
            }
            if(l2copy != nullptr){
                num2 = l2copy->val;
                l2copy = l2copy->next;
            }
            else{
                num2 = 0;
            }
            int num = num1 + num2 + jw;

            jw = num /10;
            num %= 10;

            ListNode* newnode = new ListNode(num,p);
            p = newnode;
        }

        return p;
    }
};

思路二 利用栈

上面的反转链表的目的就是为了得到链表从后往前的数字顺序，这个结构是不是可以借助栈实现。
嗯，这么一说，是不是就有思路了。

// 利用栈

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> num1,num2;
        while(l1 != nullptr){
            num1.push(l1->val);
            l1 = l1->next;
        }

        while(l2 != nullptr){
            num2.push(l2->val);
            l2 = l2->next;
        }

        int jw = 0;
        ListNode* p = nullptr;

        while(num1.empty() == false || num2.empty() == false || jw){
            int n1 =num1.empty() ? 0 : num1.top();
            int n2 = num2.empty() ? 0 :num2.top();
            if(!num1.empty())   num1.pop();
            if(!num2.empty())   num2.pop();

            int num = n1 + n2 + jw;
            jw = num / 10;
            num = num % 10;

            ListNode* newnode = new ListNode(num,p);
            p = newnode;
        }

        return p;
    }
};

其实还有一种思路是先将两个链表转换为数字，相加之后再存入链表。不过我实践后发现会超出范围，我最后使用 long long 类型依旧不能满足，所以放弃了，大家可以试一试。欢迎留言交流。