2.两数之和

使用两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。即每个数字位的值都是有效的，例如 60 不会表示为 060。

解题思路：链表求和

这里首先想到的，是将链表转换成具体的数字，相加，再将具体的数字转换为链表，具体的实现如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    v1 := getValue(l1)
    v2 := getValue(l2)
    s := v1 + v2
    return makeNode(s)
}

func getValue(node *ListNode) int {
    v := 0
    base := 0
    for {
        vb := math.Pow10(base)
        v += node.Val * int(vb)
        base++
        if node.Next == nil {
            break
        }
        node = node.Next
    }
    return v
}

func makeNode(v int) *ListNode {
    list := make([]int, 0)
    for {
        rem := v % 10
        list = append(list, rem)
        if v < 10 {
            break
        }
        v = (v - rem) / 10
    }

    if len(list) == 0 {
        return nil
    }
    res := &ListNode{
        Val: list[0],
    }
    temp := res
    for i := 1; i < len(list); i++ {
        temp.Next = &ListNode{Val: list[i]}
        temp = temp.Next
    }
    return res
}

在一定范围内，这样的实现是可行的，而且在我看来，这样实现最大的好处是直观，但显然 LeetCode 不这样认为！

数字直接相加走不通，那么，还是直接链表相加吧，这里要考虑进位的问题，代码实现如下：

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry, head := 0, l1
    for {
        // 值相加再加进位
        l1.Val += l2.Val + carry
        // 进位
        carry = l1.Val / 10
        // 求余
        l1.Val %= 10
        if l2.Next == nil {
            break
        } else if l1.Next == nil {
            // 将 l2 的链表阶段接到 l1 上
            l1.Next = l2.Next
            break
        }
        // 执行链表中的下一项
        l1 = l1.Next
        l2 = l2.Next
    }

    // 如果前面的进位没有用到
    for carry != 0 {
        if l1.Next == nil {
            l1.Next = &ListNode{0, nil}
        }
        l1.Next.Val += carry
        carry = l1.Next.Val / 10
        l1.Next.Val %= 10
        l1 = l1.Next
    }

    return head
}

既然链表可以实现，那么直接用数组呢？

// 数组转换为链表
func makeNodeByList(list []int) *ListNode {
    if len(list) == 0 {
        return nil
    }
    res := &ListNode{
        Val: list[0],
    }
    temp := res
    for i := 1; i < len(list); i++ {
        temp.Next = &ListNode{Val: list[i]}
        temp = temp.Next
    }
    return res
}

// 链表转换为数组
func nodeToList(node *ListNode) []int {
    r := make([]int, 0)
    for {
        if node == nil {
            break
        }
        r = append(r, node.Val)
        node = node.Next
    }
    return r
}

// 数组相加
func addTwoList(l1, l2 []int) []int {
    minList := l1
    maxList := l2
    if len(l1) > len(l2) {
        minList = l2
        maxList = l1
    }
    r := maxList
    for i := range minList {
        r[i] = maxList[i] + minList[i]
    }
    for i, v := range r {
        if v >= 10 {
            r[i] -= 10
            if i < len(r)-1 {
                r[i+1]++
            } else {
                r = append(r, 1)
            }
        }
    }
    return r
}

// 这里返回结果
func addTwoNumsList(l1 *ListNode, l2 *ListNode) *ListNode {
    list1 := nodeToList(l1)
    list2 := nodeToList(l2)
    list := addTwoList(list1, list2)
    return makeNodeByList(list)
}

事实证明，虽然链表的空间占用率较小，但是数组的时间复杂度更低，至少 LeetCode 是这样认为的。

最后贴一张数组运行的结果图。

附

下一题传送门