两数相加
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 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))
}
}
