58.两数相加
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
- 输入：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
- 题目数据保证列表表示的数字不含前导零
思路
题目说每个节点的值都在0~9里面，所以只考虑个位数就好。
2 -> 4 -> 3 表示 342
5 -> 6 -> 4 表示 465
---------------------
7 -> 0 -> 8 表示807
其实就是模拟小学竖式加法，先从个位开始逐位相加，记住进位。
3 4 2
4 6 5
-------
8 0 7
每一位: 当前位的值 = (l1当前位的值 + l2当前位的值 + 进位) % 10
进位: carry = (l1当前位的值 + l2当前位的值 + 进位) / 10
class Solution {
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
var l1NodeIndex = l1
var l2NodeIndex = l2
// 进位
var carry = 0
// 头结点
var head: ListNode? = null
// 记录当前节点
var curr: ListNode? = null
while (l1NodeIndex != null || l2NodeIndex != null || carry != 0) {
val sum = (l1NodeIndex?.`val` ?: 0) + (l2NodeIndex?.`val` ?: 0) + carry
carry = sum / 10
val node = ListNode(sum % 10)
if (head == null) {
head = node
curr = node
} else {
curr!!.next = node
curr = node
}
l1NodeIndex = l1NodeIndex?.next
l2NodeIndex = l2NodeIndex?.next
}
return head
}
class ListNode(var `val`: Int) {
var value: Int = 0
var next: ListNode? = null
}
}
复杂度
- 时间复杂度:O(max(m,n))：m、n 是两个链表的长度，最多遍历较长的那个。
- 空间复杂度:O(max(m,n))：结果链表的长度最多是 max(m,n)+1。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!