题目描述

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

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

2 → 4 → 3

5 → 6 → 4

7 → 0 → 8

输入：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]

原题目链接：https://leetcode-cn.com/problems/add-two-numbers/

解法

这道题是简单的链表相加题，而且题意非常贴心的把数字的顺序反过来了，这样更有利于相加。

因为我们处理相加本来就是从低位到高位进行，遇到单个十进制位加法结果大于十，则会做进位处理。

本题主要是考察开发者对链表的编码应用。

我的通过代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        // 变量 b1 和 b2 存放 l1 和 l2 的链表移动指针
        var b1 = l1
        var b2 = l2

        // 变量 sumNode 存放相加之和的链表移动指针
        let sumNode = ListNode()

        // 变量 iter 存放相加之和的链表移动指针
        var iter: ListNode? = sumNode

        // 变量 addNext 存放是否相加后获得一个进位
        var addNext = false

        // b1 和 b2 初始化为 l1 和 l2 的首指针，进入循环
        while b1 != nil || b2 != nil || addNext {
            // b1 和 b2 指针相加，其中如果有任意一个指针为空，说明该指针前面没有数字了。
            // 没有数字的指针即可以当 0 处理。
            // 如果存在 addNext，说明上一轮数字相加有进位，那么要额外加一。
            var sum = (b1?.val ?? 0) + (b2?.val ?? 0) + (addNext ? 1 : 0)
            if sum >= 10 {
                // 相加结果大于等于 10 的时候，做进位处理，并且当前位保留个位数
                sum = sum % 10
                addNext = true
            } else {
                // 相加结果小于 10，则不做进位处理
                addNext = false
            }

            iter?.val = sum
            // 分别将 b1 和 b2 往前移动
            // 这里利用了`swift`语言的`optional`特性，其它语言就要做空指针判定
            b1 = b1?.next
            b2 = b2?.next

            // 当 b1 不为空 或者 b2 不为空 或者存在进位时，说明加数还有一位
            // iter往前移动
            if b1 != nil || b2 != nil || addNext {
                let next = ListNode()
                iter?.next = next
                iter = next
            }
        }
        
        return sumNode
    }
}