Fork me on GitHub

Leetcode: 2.Add Two Numbers

发表于 | 分类于 
这是崔斯特的第八十九篇原创文章

2. Add Two Numbers

难度: Medium

刷题内容

原题连接：https://leetcode.com/problems/add-two-numbers/description/>

内容描述

1
2
3
4
5
6
7
8
9
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.

解题方案 Python

思路 1

  • 时间复杂度: O(N)
  • 空间复杂度: O(N)

将两个链表转为列表，反转之后相加，再反转，最后将结果转为链表。 

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        
        val1, val2 = [l1.val], [l2.val]
        while l1.next:
            val1.append(l1.next.val)
            l1 = l1.next
        while l2.next:
            val2.append(l2.next.val)
            l2 = l2.next
            
        num1 = ''.join([str(i) for i in val1[::-1]])
        num2 = ''.join([str(i) for i in val2[::-1]])
        
        tmp = str(int(num1) + int(num2))[::-1]
        res = ListNode(int(tmp[0]))
        run_res = res
        for i in range(1, len(tmp)):
            run_res.next = ListNode(int(tmp[i]))
            run_res = run_res.next
        return res

result：

1
2
3
Runtime: 124 ms, faster than 33.23% of Python3 online submissions for Add Two Numbers.
Memory Usage: 13.4 MB, less than 5.21% of Python3 online submissions for Add Two Numbers.

这是最简单的解法，但是面试官往往不会满足，他肯定还会问，你还有简单的解法吗？空间复杂度可以再低一些吗？

思路2

  • 时间复杂度: O(N)
  • 空间复杂度: O(1)

可以使用递归，每次算一位的相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 and not l2:
            return 
        elif not (l1 and l2):
            return l1 or l2
        else:
            if l1.val + l2.val < 10:
                l3 = ListNode(l1.val+l2.val)
                l3.next = self.addTwoNumbers(l1.next, l2.next)
            else:
                l3 = ListNode(l1.val+l2.val-10)
                l3.next = self.addTwoNumbers(l1.next, self.addTwoNumbers(l2.next, ListNode(1)))
        return l3

Result:

1
2
Runtime: 116 ms, faster than 42.88% of Python3 online submissions for Add Two Numbers.
Memory Usage: 13.3 MB, less than 5.21% of Python3 online submissions for Add Two Numbers.

Golang

这个问题比较简单，基本上解题思路是比较清晰的。输入是两个链表，链表的元素都是单个数字（0-9），要求将两个列表的相应节点数字相加，并作为结果链表返回。

这个题咋看可以马上开始解答，但是在此之前还是有一些需要注意的地方。第一点是，题目并没有说明链表的长度，所以 A 和 B 两个链表可能不一定相同长度，那么如果一个链表更长，那么相加怎么处理呢？这里就考虑直接返回即可，相当于+0。第二点是，如果相加溢出怎么处理，其实题目的例子里面已经很清晰了，溢出会发生进位，依次向后处理。第三点是，如果最后一位发生进位呢，这点容易被遗忘，需要新增一个节点。

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
package add_two_numbers
type ListNode struct {
	Val 	int
	Next	*ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	resPre := &ListNode{}
	cur := resPre
	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 resPre.Next
}

测试

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package add_two_numbers
import (
	"github.com/stretchr/testify/assert"
	"testing"
)
type para struct {
	one *ListNode
	two *ListNode
}
type ans struct {
	one *ListNode
}
type question struct {
	p para
	a ans
}
func makeListNode(is []int) *ListNode {
	if len(is) == 0 {
		return nil
	}
	res := &ListNode{
		Val: is[0],
	}
	temp := res
	for i := 1; i < len(is); i++ {
		temp.Next = &ListNode{Val: is[i]}
		temp = temp.Next
	}
	return res
}
func Test_OK(t *testing.T)  {
	ast := assert.New(t)
	qs := []question{
		{
			p: para{
				one:makeListNode([]int{2, 4, 3}),
				two:makeListNode([]int{5, 6, 4}),
			},
			a: ans{
				one:makeListNode([]int{ 7, 0, 8}),
			},
		},
		{
			p: para{
				one:makeListNode([]int{9, 8, 7, 6, 5}),
				two:makeListNode([]int{1, 1, 2, 3, 4}),
			},
			a:ans{
				one:makeListNode([]int{0, 0, 0, 0, 0, 1}),
			},
		},
		{
			p: para{
				one:makeListNode([]int{0}),
				two:makeListNode([]int{5, 6, 4}),
			},
			a: ans{
				one:makeListNode([]int{5, 6, 4}),
			},
		},
	}
	for _, q := range qs {
		a, p := q.a, q.p
		ast.Equal(a.one, addTwoNumbers(p.one, p.two), "输入:%v", p)
	}
}

消耗

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	sum := l1.Val + l2.Val
	val := sum % 10
	if (l1.Next == nil && l2.Next == nil && sum < 10) {
		return &ListNode{sum, nil}
	}
	if (l1.Next == nil) {
		l1.Next = &ListNode{}
	}
	if (l2.Next == nil) {
		l2.Next =  &ListNode{}
	}
	if  (sum >= 10) {
		l1.Next.Val += 1
	}
	res := addTwoNumbers(l1.Next, l2.Next)
	return &ListNode{val, res}
}

有时候很无语，同样的解法，提交时间不一样，性能差别竟然有这么大，12ms与20ms。(⊙_⊙)?