题目

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

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

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

示例：

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

说明

链表的节点按如下定义

type ListNode struct {
    Val  int
    Next *ListNode
}

解答

注意处理进位。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var (
        t1 *ListNode = l1
        t2 *ListNode = l2
        p  *ListNode
    )

    // 为编写代码方便，设立一个哑节点
    ret := &ListNode{
        Val:  0,
        Next: nil,
    }
    p = ret

    var (
        x     int
        y     int
        carry int = 0
        s     int = 0
    )

    for t1 != nil || t2 != nil {
        if t1 != nil {
            x = t1.Val
        } else {
            x = 0
        }
        if t2 != nil {
            y = t2.Val
        } else {
            y = 0
        }

        s = x + y + carry
        carry = s / 10

        p.Next = &ListNode{
            Val:  s % 10,
            Next: nil,
        }
        p = p.Next

        if t1 != nil {
            t1 = t1.Next
        }
        if t2 != nil {
            t2 = t2.Next
        }
    }

    if carry != 0 {
        p.Next = &ListNode{
            Val:  carry,
            Next: nil,
        }
    }

    // 把哑节点去掉再返回
    ret = ret.Next
    return ret
}

用来创建测试用数据的函数

func createTestData(a []int, b []int) (*ListNode, *ListNode) {
    const textErr = "bad param"
    if a == nil || b == nil {
        panic(textErr)
    }
    m, n := len(a), len(b)
    if m == 0 || n == 0 {
        panic(textErr)
    }
    if (a[0] == 0 && m != 1) || (b[0] == 0 && n != 1) {
        panic(textErr)
    }
    for i := 0; i < m; i++ {
        if a[i] < 0 || a[i] > 9 {
            panic(textErr)
        }
    }
    for i := 0; i < n; i++ {
        if b[i] < 0 || b[i] > 9 {
            panic(textErr)
        }
    }
    var l1 *ListNode
    var l2 *ListNode
    var p *ListNode
    var q *ListNode
    for i := 0; i < m; i++ {
        p = &ListNode{
            Val:  a[i],
            Next: nil,
        }
        if i == 0 {
            q = p
            l1 = p
        } else {
            q.Next = p
            q = p
        }
    }
    for i := 0; i < n; i++ {
        p = &ListNode{
            Val:  b[i],
            Next: nil,
        }
        if i == 0 {
            q = p
            l2 = p
        } else {
            q.Next = p
            q = p
        }
    }
    return l1, l2
}