两数相加

002_add_two_numbers

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

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

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出:7 -> 0 -> 8

原因:342 + 465 = 807

这道题就是用定义的单链表类来做个简单的计算,没啥很精妙的思路

1.模拟竖式加法&~

最暴力,加数全往carry里塞,用p做结果指针

hist:

  • 最初写的时候是先加一个空节点,算完再往里放数据,这会导致链表后面多空一个节点.

去最后一个空节点挺麻烦,所以把第0个节点留空,也就是先计算,再加节点

  • 增加了一个 先判断是否有一个链表是空的
class Solution:
    def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
      if not l1 : return l2
      if not l2 : return l1
      result = p = ListNode(0)
      carry = 0
      while l1 or l2 or carry:
        if l1:
          carry += l1.val
          l1 = l1.next
        if l2:
          carry +=l2.val
          l2 = l2.next
        p.next = ListNode(carry%10)
        p = p.next
        carry //=10
      return result.next
136ms 6.7MB 74.95% 89.22%

2.蟒蛇语偷懒法

大力法,变整数,加完再变回链表(蠢)

(这里还有一种做法是用字符串来拼接)

class Solution:
    def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
      num1,num2 = 0,0
      count = 0
      while l1:
        num1 += l1.val*(10**count)
        l1 = l1.next
        count+=1
      count = 0
      while l2:
        num2 += l2.val*(10**count)
        l2 = l2.next
        count+=1
      add_num = num1+num2
      result = p = ListNode(-1)
      for i in range(len(str(add_num))):
        p.next = ListNode(add_num%10)
        p = p.next
        add_num = add_num//10
      return result.next

216ms 6.7MB | 7.81% 89.22% 这里发生了一个奇怪的事情,多次提交时间变化很大,132~216ms都有


3.炫酷递归

搜到了一个递归的算法,是C++写的,我用python重写了,但感觉只是在秀操作(我感觉基础问题递归很多时候都不太友好,只有在二叉树之类的地方有较大用处)

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        int target = l1->val + l2->val;
        ListNode* res = new ListNode(target % 10);
        res->next = addTwoNumbers(l1->next, l2->next);
        if (target >= 10)
            res->next = addTwoNumbers(res->next, new ListNode(1));
        delete l1, l2;
        return res;
    }
};
class Solution:
    def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
      if not l1 : return l2
      if not l2 : return l1
      target = l1.val +l2.val
      result = ListNode(target%10)
      result.next = self.addTwoNumbers(l1.next,l2.next)
      if target >=10:
        result.next = self.addTwoNumbers(result.next,ListNode(1))
      return result
172ms 6.7MB 39.89% 62.98%
本文总字数: 1804