正文
iOS 面试题（13）：求两个链表表示的数的和
原创
2017-02-07
唐巧
iOS开发by唐巧
问题
给你两个链表，分别表示两个非负的整数。每个链表的节点表示一个整数位。
为了方便计算，整数的低位在链表头，例如：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 纸才写完。
这道题其实完全不考查什么「算法」，人人都知道怎么计算，但是它考察了「将想法转换成代码」的能力，新手通常犯的毛病就是：意思都明白，但是写不出来代码。所以，这类题目用来过滤菜鸟确实是挺有效的办法。
答案
本题的做法其实没什么特别，就是直接计算。计算的时候需要考虑到以下这些情况：
两个整数长度不一致的情况。
