两数相加

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

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

leetcode2.png

示例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
• 题目数据保证列表表示的数字不含前导零

思路

• 同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。比如：如果当前两个链表处相应位置的数字为 n1,n2，进位值为carry，则它们的和为n1+n2+carry；其中，链表处相应位置的数字为 (n1+n2+carry)%10，而新的进位值为(n1+n2+carry)/10

• 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0

• 此外，如果链表遍历结束后，有carry>0，还需要在链表的后面附加一个节点，节点的值为carry

链表

public class ListNode {
    public var value: Int
    public var next: ListNode?

    public init() {
        self.value = 0;
        self.next = nil;
    }

    public init(_ value: Int) {
        self.value = value;
        self.next = nil;
    }

    public init(_ value: Int, _ next: ListNode?) {
        self.value = value;
        self.next = next;
    }
}

遍历

// 44ms 13.7MB
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var listNode1 = l1
    var listNode2 = l2
    let headNode: ListNode = ListNode() // 头节点
    var tailNode: ListNode = headNode // 尾节点
    var carry = 0 // 进位值(两个数相加大于等于10时，将十位数上的值赋给进位值，并参与下一节点的求和)

    // 遍历链表
    while listNode1 != nil || listNode2 != nil  {
        let sum = (listNode1?.value ?? 0) + (listNode2?.value ?? 0) + carry

        tailNode.next = ListNode(sum % 10)  // 保存本次遍历的节点

        // 获取链表的下一个节点
        listNode1 = listNode1?.next
        listNode2 = listNode2?.next

        carry = sum / 10   // 更新进位值

        tailNode = tailNode.next!     // 移动尾节点
    }

    if carry > 0 { // 最后可能存在进位值
        tailNode.next = ListNode(carry)
    }

    return headNode.next
}

递归

// 44ms 13.3MB
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    if l1 == nil && l2 == nil {
        return nil
    } else {
        var sum = (l1?.value ?? 0) + (l2?.value ?? 0) // 计算当前值和
        
        var next1: ListNode? = l1?.next // 取l1链表的下一节点，nil亦可
        if sum > 9 { // 存在进1标识位
            next1 = ListNode((l1?.next?.value ?? 0) + (sum / 10), l1?.next?.next) // 把1加到下个节点的val
            sum = sum % 10   // 取余，如：13 % 10，sum = 3
        }
        return ListNode(sum, addTwoNumbers1(next1, l2?.next))
    }
}

参考

• add-two-numbers
• leetcode