LeetCode-445.两数相加II

发表于 分类于

题目描述

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1

1
2
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2

1
2
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3

1
2
输入：l1 = [0], l2 = [0]
输出：[0]
  • 链表的长度范围为 [1, 100]
  • 0 <= node.val <= 9
  • 输入数据保证链表代表的数字无前导 0

题解

思路：将两个链表节点的值分别入栈，然后依次pop出来后相加，拼接起来形成新的链表

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
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
  var list1 = stackFor(l1)
  var list2 = stackFor(l2)
  var cur: ListNode? = nil
  var carry = 0
  while list1.count > 0 || list2.count > 0 || carray > 0 {
    var sum = 0
    if let value = list1.popLast() {
      sum += value
    }
    if let value = list2.popLast() {
      sum += value
    }
    sum += carry
    carry = sum / 10
    // 新节点拼接到前面
    let temp = cur
    cur = ListNode(sum % 10)
    cur?.next = temp
  }
  
  return cur
}
/** 将链表节点的值依次入栈 */
func stackFor(_ head: ListNode?) -> [Int] {
  var list: [Int] = []
  var cur = head
  while cur !== nil {
    list.append(cur!.val)
    cur = cur?.next
  }
  return list
}