leetcode-两数相加

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

请你将两个数相加，并以相同形式返回一个表示和的链表。
示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

分析
考虑两个问题，

1. 链表长度
   链表长度一样，每次循环都可以直接相加，如果长度不一样，我们需要默认补零，这一点很关键，也就是每次循环我们需要确定相加的数字具体是多少；
2. 进位，因为每次相加都是从低位开始，进位需要在下一位相加的时候加进去，最后一次如果仍然有进位，需要把进位放到链表末尾。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    var res *ListNode
    var tail *ListNode
    var carry = 0

    for l1 != nil || l2 != nil {
        sum := 0
        var n1, n2 = 0, 0

        if l1 != nil {
            n1 = l1.Val
            l1 = l1.Next
        }

        if l2 != nil {
            n2 = l2.Val
            l2 = l2.Next
        }
        // 加入进位值
        sum = n1 + n2 + carry

        // 计算当前位数字和以及进位值
        sum, carry = sum%10, sum/10

        if res == nil {
            // 初次赋值
            res = &ListNode{Val: sum}
            tail = res  // 此处赋值，tail指向res的地址
        } else {
            // 当前赋值
            tail.Next = &ListNode{Val: sum}
            // 下一次置空
            tail = tail.Next
        }
    }
        // 将进位添加到链表末尾
    if carry > 0 {
        tail.Next = &ListNode{Val: carry}
    }
    return res
}

该算法时间复杂度O(max(m,n)) 取决于两个链表的长度最大值，空间复杂度为O(1)。
里面涉及一个比较简单的基础知识：插入链表，也就是链表的更新
简化代码如下：

func InsertList() *ListNode {
    var res *ListNode
    var tail *ListNode
    var sum int
    for {
        if res == nil {
            res = &ListNode{Val: sum}
            tail = res
        } else {
            tail.Next = &ListNode{Val: sum}
            tail = tail.Next
        }
        sum++
        if sum >= 10 {
            return res
            break
        }
    }
    return nil
}

res可以看作头节点，tail看作尾节点，第一次初始化头节点和尾节点，后续每次只需要将新节点更新到尾节点，并将尾节点更新成新节点，整个链表则完成了链接。