剑指OfferII025.链表中的两数相加

题目

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

将这两数相加会返回一个新的链表。

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

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

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

示例3：输入：l1 = [0], l2 = [0] 输出：[0]

提示：链表的长度范围为 [1, 100]

0 <= node.val <= 9

输入数据保证链表代表的数字无前导 0

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

注意：本题与主站 445 题相同：

解题思路分析

1、反转遍历；时间复杂度O(n)，空间复杂度O(n)

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   l1 = reverse(l1)
   l2 = reverse(l2)
   res := &ListNode{}
   cur := res
   carry := 0
   for l1 != nil || l2 != nil || carry > 0 {
      sum := carry
      if l1 != nil {
         sum += l1.Val
         l1 = l1.Next
      }
      if l2 != nil {
         sum += l2.Val
         l2 = l2.Next
      }
      carry = sum / 10 // 进位
      cur.Next = &ListNode{Val: sum % 10}
      cur = cur.Next
   }
   return reverse(res.Next)
}

func reverse(head *ListNode) *ListNode {
   var result *ListNode
   var temp *ListNode
   for head != nil {
      temp = head.Next
      head.Next = result
      result = head
      head = temp
   }
   return result
}

2、栈辅助；时间复杂度O(n)，空间复杂度O(n)

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   stack1 := make([]int, 0)
   stack2 := make([]int, 0)
   for l1 != nil {
      stack1 = append(stack1, l1.Val)
      l1 = l1.Next
   }
   for l2 != nil {
      stack2 = append(stack2, l2.Val)
      l2 = l2.Next
   }
   var res *ListNode
   carry := 0
   for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
      if len(stack1) > 0 {
         carry = carry + stack1[len(stack1)-1]
         stack1 = stack1[:len(stack1)-1]
      }
      if len(stack2) > 0 {
         carry = carry + stack2[len(stack2)-1]
         stack2 = stack2[:len(stack2)-1]
      }
      temp := &ListNode{
         Val:  carry % 10,
         Next: res,
      }
      carry = carry / 10
      res = temp
   }
   return res
}

3、递归；时间复杂度O(n)，空间复杂度O(n)

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
   a, b := l1, l2
   length1, length2 := 0, 0
   for a != nil {
      length1++
      a = a.Next
   }
   for b != nil {
      length2++
      b = b.Next
   }
   res, carry := add(l1, l2, length1, length2)
   if carry > 0 {
      return &ListNode{Val: carry, Next: res}
   }
   return res
}

func add(l1, l2 *ListNode, length1, length2 int) (res *ListNode, carry int) {
   if l1 != nil && l2 != nil {
      if l1.Next == nil && l2.Next == nil {
         val := l1.Val + l2.Val
         carry = val / 10
         res = &ListNode{Val: val % 10, Next: nil}
         return
      }
   }
   a := &ListNode{}
   var b, n int
   if length1 > length2 {
      a, b = add(l1.Next, l2, length1-1, length2)
      n = l1.Val + b
   } else if length1 < length2 {
      a, b = add(l1, l2.Next, length1, length2-1)
      n = l2.Val + b
   } else {
      a, b = add(l1.Next, l2.Next, length1-1, length2-1)
      n = l1.Val + l2.Val + b
   }
   res = &ListNode{Val: n % 10, Next: a}
   carry = n / 10
   return
}