李洪强iOS经典面试题34-求两个链表表示的数的和

问题

给你两个链表，分别表示两个非负的整数。每个链表的节点表示一个整数位。

为了方便计算，整数的低位在链表头，例如：123 在链表中的表示方式是：

3 -> 2 -> 1

现在给你两个这样结构的链表，请输出它们求和之后的结果。例如：

输入: (2 -> 4 -> 1) + (5 -> 6 -> 1)
输出: 7 -> 0 -> 3

代码模版

本题的 Swift 代码模版如下：

private class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) 
         -> ListNode? {

    }
}

考查点

本题出自 LeetCode 上的第 2 题。

这是我高中学习编程时最早接触的一类题目，我们把这类题目叫做「高精度计算」，其实就是在计算机计算精度不够时，模拟我们在纸上演算的方式来计算答案，然后获得足够精度的解。

我还记得我 7 年前第一次去网易有道面试的时候，就考查的是一道类似的高精度计算题目，比这道题复杂得多，我当时用了一个比较笨的办法，加上当时还是用 C++ 写的，内存分配和释放写起来也比较麻烦，最后写了两页 A4 纸才写完。

这道题其实完全不考查什么「算法」，人人都知道怎么计算，但是它考察了「将想法转换成代码」的能力，新手通常犯的毛病就是：意思都明白，但是写不出来代码。所以，这类题目用来过滤菜鸟确实是挺有效的办法。

答案

本题的做法其实没什么特别，就是直接计算。计算的时候需要考虑到以下这些情况：

两个整数长度不一致的情况。
进位的情况。当进位产生时，我们需要保存一个标志位，以便在计算下一位的和的时候，加上进位。
当计算完后，如果还有进位，需要处理最后结果加一位的情况。

以下是完整的代码，我使用了一些 Swift 语言的特性，比如用 flatMap 来减少对于 Optional类型值为 nil 的判断。

private class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

private class Solution {

    private func getNodeValue(_ node: ListNode?) -> Int {
        return node.flatMap { $0.val } ?? 0
    }

    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) 
             -> ListNode? {
        if l1 == nil || l2 == nil {
            return l1 ?? l2
        }
        var p1 = l1
        var p2 = l2
        let result: ListNode? = ListNode(0)
        var current = result
        var extra = 0
        while p1 != nil || p2 != nil || extra != 0 {
            var tot = getNodeValue(p1) +
                      getNodeValue(p2) + extra
            extra = tot / 10
            tot = tot % 10
            let sum:ListNode? = ListNode(tot)
            current!.next = sum
            current = sum
            p1 = p1.flatMap { $0.next }
            p2 = p2.flatMap { $0.next }
        }
        return result!.next
    }
}

以上代码也可以从我的 Gist 中找到：https://gist.github.com/tangqiaoboy/af0dc9a45dd309e91436b44b76eab5f1

偷偷告诉你一个小秘密，Gist 里面的代码我稍微修改了两行，最终性能就从打败 LeetCode 10% 的提交变成了打败 LeetCode 50% 的提交，如果你感兴趣，可以自己仔细对比一下。

愿大家玩得开心～