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

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807

解题思路

首先想到的解决思路是将链表中的数转化为数据类型，然后加起来（可能会发生越界问题），再转化为链表。

class Solution:    def addTwoNumbers(self, l1, l2):        """        :type l1: ListNode        :type l2: ListNode        :rtype: ListNode        """               def get_num(l):            num = 0            t = 1            while l != None:                l, val = l.next, l.val                num += val*t                t *= 10            return num        l3 = get_num(l1) + get_num(l2)        ret = t = ListNode(0)                if l3 == 0:            return ret                while l3 != 0:            n = l3 % 10            t.next = ListNode(n)            t = t.next            l3 //= 10        return ret.next

但是这个解法是如此的丑陋！！！

那么能不能不把链表中的数据转化为ListNode，而直接在它的基础上进行加法呢？我们这样去做的话，会遇到这样的一个问题，当两个数的和大于10 的时候，他们相加的结果就会进位，所以要解决的问题就是这个进位问题。

class Solution:    def addTwoNumbers(self, l1, l2):        """        :type l1: ListNode        :type l2: ListNode        :rtype: ListNode        """        cur = ret = ListNode(0)        add = 0                while l1 or l2 or add:            val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + add            add = val // 10            cur.next = ListNode(val % 10)            cur = cur.next            l1 = l1.next if l1 else None            l2 = l2.next if l2 else None                return ret.next

我们通过添加一个变量add去记录这个进位的值。这样我们的代码变得比之前简洁了很多。

我在这里同时给出对应的c++版本。

class Solution {
   public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)     {
           ListNode* dumHead = new ListNode(0);        ListNode* p = dumHead;        int add = 0;        while (l1 || l2 || add)        {
               int val = get_value(l1) + get_value(l2) + add;            add = val / 10;            p->next = new ListNode(val % 10);            p = p->next;            l1 = get_p(l1);            l2 = get_p(l2);        }        ListNode* ret = dumHead->next;        delete dumHead;        return ret;    }private:    int get_value(ListNode* l)    {
           if (l != nullptr) return l->val;        else return 0;    }    ListNode* get_p(ListNode* l)    {
           if (l != nullptr) return l->next;        return nullptr;    }};

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/80435080 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！