Leetcode 2 - Add Two Numbers

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

Question

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Analysis

这一道题在一刷的时候还没有特别的解决技巧，基本思路是分为三种情况：

  1. 两个链表节点都有值的时候，将两个节点的值加起来赋给新节点；
  2. 只有链表一的节点有值，将链表一节点的值赋给新节点
  3. 只有链表二的节点有值，将链表一节点的值赋给新节点
    这是最先想到的解法，代码在下方 Method One 中展示。

比较简化的思路是，只要链表一或者链表二存在有效值，就继续循环。如果链表一有值而链表二没有，则给链表二的节点赋值 ListNode(0) 用于计算；反之给链表一的节点赋值 ListNode(0)。这样操作省去了分情况讨论的复杂性，这个算法的代码在 Method Optimum 中展示。另外需要注意的是，当两个值相加超过9时，仅保留个位上的数字，并进位，因此需要额外的空间保存进位信息。

Code

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
43
44
45
46
47
class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # Method Two
        temp = ListNode(0)
        res = temp
        carry = 0
        while l1 is not None or l2 is not None:
            l1 = l1 or ListNode(0)
            l2 = l2 or ListNode(0)
            total = l1.val+l2.val+carry
            carry = total//10
            total %= 10
            l1 = l1.next
            l2 = l2.next
            temp.next = ListNode(total)
            temp = temp.next
        if carry == 1:
            temp.next = ListNode(1)
        return res.next 
        
        # Method One
        # temp = ListNode(0)
        # res = temp
        # addOne = 0
        # while(l1 or l2 or addOne):
        #     temp.next = ListNode(0)
        #     temp = temp.next
        #     if l1 and l2:
        #         temp.val = l1.val+l2.val+addOne
        #         l1 = l1.next
        #         l2 = l2.next
        #     elif l1:
        #         temp.val = l1.val+addOne
        #         l1 = l1.next
        #     elif l2:
        #         temp.val = l2.val+addOne
        #         l2 = l2.next
        #     else:
        #         temp.val = 1
        #     addOne = temp.val // 10
        #     temp.val %= 10
        # return res.next
Comments