leetcode - 2. 两数相加[Swift]
2022-04-18 本文已影响0人
Kegem
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 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
- 题目数据保证列表表示的数字不含前导零
解题思路
其实这里没多么复杂的逻辑在里面，就是两个链表同一位位置的数值相加即可，但是这里需要考虑进位的问题，也就是说该位置下值的和还需要加上进位的值，才是当前位置下的值的和sum = l1.value + l2.value + 进位的值，那么对应新链表同一位置下的值就是sum % 10，取余的原因就是大于10要进位，题目中说了，每个节点只能存储一位数字，那么下一个进位的值就是carry = sum / 10。根据这个思路下面给出代码。
解题代码
class ListNode {
var val: Int = 0
var next: ListNode? = nil
init() {
self.val = 0
self.next = nil
}
init(_ val: Int) {
self.val = val
self.next = nil
}
init(_ val: Int, _ next: ListNode?) {
self.val = val
self.next = next
}
}
struct Leetcode2 {
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
// leetcode上给的函数不支持改动，故这里需要重新赋值
var node1 = l1
var node2 = l2
// 新链表的表头，也是最后返回的值
var newNode: ListNode?
// 新链表的表尾
var tailNode: ListNode?
// 进位
var carry: Int = 0
// 循环链表
while node1 != nil || node2 != nil {
// 取出l1的值，当不存在该节点时，补0
let l1Value = node1?.val ?? 0
// 取出l2的值，当不存在该节点时，补0
let l2Value = node2?.val ?? 0
// 计算两值之和 + 进位的值 = 该节点的最终的和值
let sum = l1Value + l2Value + carry
// 确定新链表表头
if newNode == nil {
newNode = ListNode(sum % 10)
// 这是是第一个节点 故表头和表尾是同一个节点
tailNode = newNode
} else {
// 当新的链表已经存在时，当前的尾部节点的next就是新的节点
tailNode?.next = ListNode(sum % 10)
// 更新尾节点
tailNode = tailNode?.next
}
// 下一个节点的进位
carry = sum / 10
// 记录l1的下一个节点
if node1 != nil {
node1 = node1?.next
}
// 记录l2的下一个节点
if node2 != nil {
node2 = node2?.next
}
}
// 当最后的进位>0时，需要增加节点
if carry > 0 {
tailNode?.next = ListNode(carry)
tailNode = tailNode?.next
}
return newNode
}
}
