一、题目描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

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

二、解题思路

数字在链表中的存储顺序按从前到后依次是：个位，十位，百位，…
两数相加的时候，我们也是从个位数开始加的，产生进位则进到十位…
可见链表的存储顺序和我们进行加法运算的顺序是相符合的，我们只要从表头开始相加，进位进到下一位(Next节点)即可…

该题的难点主要在进位的处理上，关键点：

如果数字相加的结果 大于9 就会产生进位，
相加的时候应该是：v1+v2+进位
相加的 每一步 都可能产生进位

三、我的题解

我的 Go 语言代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil && l2 == nil{
        return nil
    }else if l1 == nil{
        return l2
    }else if l2 == nil{
        return l1
    }

    c1 := l1 //当前l1节点
    b1 := l1 //当前l1节点的前驱节点
    c2 := l2 //当前l2节点
    b := 0   //进位

    //都非空，先处理头节点
    if c1.Val + c2.Val <= 9{
        c1.Val = c1.Val + c2.Val
        c1 = c1.Next
        c2 = c2.Next
    }else{
        b = (c1.Val + c2.Val)/10
        c1.Val = (c1.Val + c2.Val)%10
        c1 = c1.Next
        c2 = c2.Next
    }

    //处理后面的节点
    for c1 != nil && c2 != nil{
        if c1.Val + c2.Val + b <= 9{
            c1.Val = c1.Val + c2.Val + b
            b = 0   //进位归0
            c1 = c1.Next
            b1 = b1.Next
            c2 = c2.Next
        }else{
            newb := (c1.Val + c2.Val + b)/10  //新的进位
            c1.Val = (c1.Val + c2.Val + b)%10
            b = newb
            c1 = c1.Next
            b1 = b1.Next
            c2 = c2.Next
        }

    }

    if b != 0{  //进位不为空
        if c1 == nil && c2 == nil{
            var newnode ListNode
            newnode.Val = b
            b1.Next = &newnode
            return l1
        }else if c2 == nil{
            for b != 0 {
                c1,b = jinwei(c1, b)
                c1 = c1.Next
            }
            return l1
        }else if c1 == nil{
            t2 := c2
            for b != 0 {
                c2,b = jinwei(c2,b)
                c2 = c2.Next
            }
            b1.Next = t2
            return l1
        }
    }else{   //进位为空，直接返回
        if c1 == nil && c2 == nil{
            return l1
        }else if c2 == nil{
            return l1
        }else if c1 == nil{
            b1.Next = c2
            return l1
        }

    }
    
    return l1
    
}

//进位函数，将进位b加到当前节点上，返回当前节点的新值和产生的新进位
func jinwei(l1 *ListNode, b int) (*ListNode,int){
    if l1.Val + b <= 9{
        l1.Val = l1.Val + b
        return l1,0
    }else{
        if l1.Next != nil{
            newb := (l1.Val + b)/10
            l1.Val = (l1.Val + b)%10
            return l1,newb
        }else{
            newb := (l1.Val + b)/10
            l1.Val = (l1.Val + b)%10
            var newnode ListNode
            newnode.Val = newb
            l1.Next = &newnode
            return l1,0
        }
    }
}