LeetCode链表篇：2.两数相加

你的名字 2022-08-30 04:07 156阅读 0赞

![eb676d7882128ca4cf901f4b989cbd37.png][]

## 一、题目 ##

链接：https://leetcode-cn.com/problems/add-two-numbers/

> 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

> 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

> 输出：7 -> 0 -> 8

> 原因：342 + 465 = 807

## 二、题解 ##

### 2.1 模拟 ###

根据题意，我们需要将两个逆序的链表进行相加，相加过程中需要考虑到对应位置的进位问题，假设两个链表分别为 l1 和 l2，其中进位的值为 flag，所以链表相加后当前位置存储的值为 (l1.val+l2.val+flag)%10，相加后需要进位的值为 (l1.val+l2.val+flag)//10。

注意：如果链表遍历结束后，flag 仍然存在，那说明链表后面还需要附加一个 flag 的节点值。

时间复杂度：O(max(m,n))，m 和 n 分别为两个链表的长度。

空间复杂度：O(max(m,n))

Python：

# Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            res=dummy=ListNode(-1)
            flag=0
            while l1 and l2:
                res.next=ListNode(l1.val+l2.val+flag)
                flag=res.next.val // 10
                res.next.val %= 10
                res=res.next
                l1=l1.next
                l2=l2.next
            
            p= l1 or l2
            while p:
                res.next=ListNode(p.val+flag)
                flag=res.next.val // 10
                res.next.val %= 10
                p=p.next
                res=res.next
            if flag:
                res.next=ListNode(1)
            return dummy.next

Go：

/**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
        res := &ListNode{Val: -1}
        dummy := res
        flag:=0
        for l1 != nil && l2 != nil{
            sum := l1.Val+l2.Val+flag
            res.Next=&ListNode{Val:sum%10}
            flag=sum/10
            res=res.Next
            l1=l1.Next
            l2=l2.Next
        }
        for l1 != nil{
            sum := l1.Val + flag
            res.Next=&ListNode{Val:sum%10}
            flag=sum/10
            res=res.Next
            l1=l1.Next
        }
        for l2 != nil{
            sum := l2.Val + flag
            res.Next=&ListNode{Val:sum%10}
            flag=sum/10
            res=res.Next
            l2=l2.Next
        }
        if flag>0{
            res.Next=&ListNode{Val:flag}
        }
        return dummy.Next
    }

![eb676d7882128ca4cf901f4b989cbd37.png][]  
如果觉得文章不错，希望大家可以扫描上方名片关注我的微信公众号噢，点赞、收藏、在看、分享就再好不过了。如果有任何建议和问题，可以在下方给我留言，我会及时回复的，同时会不定期更新更多的文章，祝我们终将自由。

[eb676d7882128ca4cf901f4b989cbd37.png]: /images/20220829/674c8a0389fa4de4920a43c03eae7b7e.png