leetcode - 2. 两数相加[Swift]

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 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
    }
}

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