add-two-numbers#2

发表于 更新于 分类于 本文字数： 381 阅读时长 ≈ 1 分钟

问题

两数相加#2

addTwoNumbers

定义方法#addTwoNumbers:

1
2
3
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    // 具体实现
}

单元测试

1
2
3
4
val num1 = listOf(2, 4, 3).toLinkedList()
val num2 = listOf(5, 6, 4).toLinkedList()
val sum = addTwoNumbers(num1, num2)
assert("${sum.toList()}" == "[7, 0, 8]")

解法

  • 将 2个链表看成长度相同的链表进行遍历，如果一个链表较短，则在前面补 0，比如 987 + 23 = 987 + 023 = 1010
  • 每一位的计算考虑上一位的进位，当前位计算结束后更新进位
  • 两个链表遍历完成后，进位为 1，则在新链表最前放添加节点 1

小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预指针 pre，该指针的下一个节点指向真正的头节点 head。
使用预指针的目的在于，链表初始化时无可用节点，而链表构造过程需要移动指针，进而导致头指针丢失，无法返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 两数相加
 */
fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {

    // 初始化一个预指针
    val pre: ListNode? = ListNode(0)
    var cur: ListNode? = pre
    var carry = 0 // 进位

    var num1 = l1
    var num2 = l2

    while (num1 != null || num2 != null) {

        val x = when (num1 == null) {
            true -> 0
            else -> num1.`val`
        }
        val y = when (num2 == null) {
            true -> 0
            else -> num2.`val`
        }
        var sum = x + y + carry

        // 计算进位
        carry = sum / 10
        // 计算和
        sum %= 10

        // 将结果串联
        cur?.next = ListNode(sum)

        // 移动 cur 指针
        cur = cur?.next

        num1?.let {
            num1 = it.next
        }

        num2?.let {
            num2 = it.next
        }
    }

    if (carry == 1) {
        cur?.next = ListNode(carry)
    }

    // 返回 pre 的下一个节点
    return pre?.next
}

参考