两数相加

题目描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

示例：

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

我的解答方式

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 当前计算节点n1 n2
    next1, next2 := l1, l2

    // 持续计算，直到迭代完两个链表的所有节点
    for next1 != nil || next2 != nil {
	// 需要注意，可能输入的两个链表长度不一致，为了方便计算，需要将短的链表补0
        if next1.Next == nil && next2.Next != nil {
            next1.Next = new(ListNode)
        }
        if next2.Next == nil && next1.Next != nil {
            next2.Next = new(ListNode)
        }
        
	// 使用l1来作为计算结果链表
        next1.Val += next2.Val
        
	// 位溢出，需要进一位，检查是否都有下一个节点，没有则补0
        if next1.Val > 9 {
            next1.Val -= 10
            
            if next1.Next == nil {
                next1.Next = new(ListNode)
            }
            if next2.Next == nil {
                next2.Next = new(ListNode)
            }
            
            next1.Next.Val += 1
        }
        
        next1, next2 = next1.Next, next2.Next
    }

    // 将l1初始节点返回
    return l1
}

总结

该题主要考察链表操作，位移、补位等。另外需要注意，题目描述中提到 它们各自的位数是按照 逆序 的方式存储的 这里其实不需要太过在意这个逆序，在我的理解来看，其实这个 逆序 其实更偏于与我计算过程中的 正序 个位溢出则下一个节点的百位 +1，免去了因为溢出补位需要进行的其他繁琐操作。总结一下解题过程中需要注意的几个地方：

• 两个链表长度可能不同，计算时需要补0
• 位溢出时可能也需要补位

PS：这里为了尽量避免使用更多的空间，直接将计算结果更新在了 l1 中并将其返回，虽然提交结果通过了，但是题目中有提到，相加计算后需要返回一个新链表，故此也让我有些疑惑这么做是否真正正确，毕竟 l1 已经发生了改变。