124 - 2 两数相加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

解答

感觉是要我模拟一下按位的加法。。保留一个进位数什么的

https://leetcode-cn.com/problems/add-two-numbers/solution/hua-jie-suan-fa-2-liang-shu-xiang-jia-by-guanpengc/

看题解，似乎要另外设定一个答案的链表，还要有个指针来跟踪。

但我总觉得不用，把答案覆盖掉l1不就行了吗？但是没能写出来。。

var addTwoNumbers = function(l1, l2) {
  let pre = new ListNode(0)
  cur = pre
  carry = 0
  while (l1 || l2) {
    let x = l1 ? l1.val : 0
    let y = l2 ? l2.val : 0
    let sum = x + y + carry
    carry = ~~(sum / 10)
    cur.next = new ListNode(sum % 10)
    cur = cur.next
    if (l1) {
      l1 = l1.next
    }
    if (l2) {
      l2 = l2.next
    }
  }
  if (carry === 1) {
    cur.next = new ListNode(carry)
  }
  return pre.next
};

Runtime: 120 ms, faster than 44.26% of JavaScript online submissions for Add Two Numbers.

Memory Usage: 38.5 MB, less than 56.94% of JavaScript online submissions for Add Two Numbers.

看题解的时候发现，Math.floor()可以用~~()来代替，也不知道为啥，反正就能行。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        pre = cur = ListNode(0)
        while l1 or l2:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            _sum = v1+v2+carry
            carry = _sum//10
            cur.next = ListNode(_sum % 10)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry == 1:
            cur.next = ListNode(carry)
        return pre.next

Runtime: 88 ms, faster than 17.60% of Python3 online submissions for Add Two Numbers.

Memory Usage: 14.2 MB, less than 5.67% of Python3 online submissions for Add Two Numbers.

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    pre := &ListNode{0, nil}
    cur := pre
    carry := 0
    for l1 != nil || l2 != nil {
        var x, y int
        if l1 != nil {
            x = l1.Val
        } else {
            x = 0
        }
        if l2 != nil {
            y = l2.Val
        } else {
            y = 0
        }
        sum := x + y + carry
        carry = sum / 10
        cur.Next = &ListNode{sum % 10, nil}
        cur = cur.Next
        if l1 != nil {
            l1 = l1.Next
        }
        if l2 != nil {
            l2 = l2.Next
        }
    }
    if carry == 1 {
        cur.Next = &ListNode{carry, nil}
    }
    return pre.Next
}

Runtime: 16 ms, faster than 20.80% of Go online submissions for Add Two Numbers.

Memory Usage: 5 MB, less than 51.22% of Go online submissions for Add Two Numbers.

go有个更加简洁的做法

https://leetcode.com/problems/add-two-numbers/discuss/307928/Go-Clear-Go-solution

不需要另外设立carry，只需全局留sum，carry值就是其除以10

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    pre := &ListNode{0, nil}
    cur := pre
    var sum int
    for l1 != nil || l2 != nil {
        sum /= 10
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }
        cur.Next = &ListNode{sum % 10, nil}
        cur = cur.Next
    }
    if sum/10 == 1 {
        cur.Next = &ListNode{1, nil}
    }
    return pre.Next
}

Runtime: 8 ms, faster than 89.62% of Go online submissions for Add Two Numbers.

Memory Usage: 4.9 MB, less than 85.37% of Go online submissions for Add Two Numbers.