算功@LeetCode:Add Two Numbers

Log

• 【170413】完成 01 版 Python 代码的书写
• 【170416】看完 Python 版参考答案，并记录思路

题目

Add Two Numbers

【题目类型备注】

链表, 数学

提交

01

【语言】

Python

【时间】

170413

【思路】

这题不难，传统的类 C 指针题，权当复习 了。主要是要把情况（根据链表的长度来划分）分清楚讨论即可：

1. 当两个链表均为空时：返回空链表
2. 当有一个为空、另一个非空时：返回非空链表
3. 当两个均非空时：若其中一个仅一位且元素为 0，返回另一个链表。否则考虑下述问题
4. 进位：当需要进位时，如何处理？
5. 长度：

+ 若两个链表长度相同，只要处理最高位的进位问题即可
+ 若两个链表长度不同，那么在跑完短链表后，如何跑完长链表；以及，跑完长链表后，需要考虑长链表最高位的进位问题

上述思路非常清晰，剩下的全是细节问题。

以及，由于 Python 的实现原因（或者说基于我个人对 Python 目前的了解程度来看），怎么处理头指针要考虑一下。

这样，就覆盖了本题所有逻辑、以及需要考虑的边角问题了。

【代码】

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        import copy
        if (l1 is None) and (l2 is None):
          return None

        elif l1 is None:
          answer = copy.copy(l2)
          return answer
        elif l2 is  None:
          answer = copy.copy(l1)
          return answer

        elif (l1.next is None) and (0 == l1.val):
          answer = copy.copy(l2)
          return answer
        elif (l2.next is None) and (0 == l2.val):
          answer = copy.copy(l1)
          return answer

        else:
          tempadd = 0
          p = l1
          q = l2
          # create the head node
          rememberHead = 0
          head = ListNode(0)
          answer = ListNode(0)
          while not ((p is None) or (q is None)):
            tempanswer = p.val + q.val + tempadd
            if tempanswer >= 10:
              tempadd = 1
              tempanswer -= 10
            else:
              tempadd = 0
            newnode = ListNode(tempanswer)
            # remember the head
            if 0 == rememberHead:
              head = newnode
              rememberHead = 1
            #
            answer.next = newnode
            answer = answer.next
            p = p.next
            q = q.next

          if (p is None) and (q is None):
            if (1 == tempadd):
              answer.next = ListNode(1)
          else:
            if p is None:
              p = q
            while not (p is None):
              tempanswer = p.val + tempadd
              if tempanswer >= 10:
                tempadd = 1
                tempanswer -= 10
              else:
                tempadd = 0
              newnode = ListNode(tempanswer)
              answer.next = newnode
              answer = answer.next
              p = p.next
            if (1 == tempadd):
              newnode = ListNode(1)
              answer.next = newnode

          answer = head

        return answer

【结果】

运行时：215 ms

报告链接：https://leetcode.com/submissions/detail/99992964/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 7.89% of python submissions.

我只想说真是不习惯用 Python 处理指针一类的问题……以及最开始没认真看题目，结果多花了差不多一倍的时间重写（逻辑没改，但是细调……），我去面壁一下……

看起来即便是用 Python 写也有更快的写法，后面还得再研究下。然后回头得再用那些高级语言重写下……

02

【语言】

C++

【时间】

【思路】

【代码】

【结果】

运行时：。。。 ms

报告链接：。。。

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

。。。

00

参考解法：

• Python
  • 简洁了许多，主要的点在于：
    • 不再额外写特殊情况的 if 判断，而融入整体逻辑中（至少包括：空链表，链表长度不等导致的尾部处理）
    • 直接让两个链表对象指针移动（我顾忌这点，因而采用了一些语句作为折衷手段，这可能增加了时间开销）
    • 使用 Python 函数 divmod() 来简化进位的处理
• [C++]。。。
• [Java]。。。

暂时先不看 C++ 和 Java 的思路，虽然总体上差不多，但还没用它们（至少之一）写一遍

自己实现一遍最优解：

+[date-language] 。。。