Add Two Numbers

题目出处

来自于leetcode

题目描述

You are given two linked lists representing two non-negative numbers. 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.

1
2
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解读

给定两个表示两个非负整数的单链表,这两个数按反序保存在单链表中,把两个数相加并返回一个单链表。
给定的例子为342 + 465 = 807

第一版答案

  1. 从两个单链表的开头相加,记住进位;
  2. 几个边界条件需要注意:
  • 入参的两个单链表有可能为空,若一个为空,则直接返回另一个即可;
  • 两个单链表长度可能不一样,在相加结束后需要把比较长的剩余的数值拷贝过去;
  • 进位也需要考虑,如5 + 5 = 10, 当两个单链表处理完毕后,如果还有进位,还需要增加一个节点

代码如下

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
# 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
"""
if not l1:
return l2
if not l2:
return l1

carry = 0
sums = l1.val + l2.val + carry
carry = sums / 10
res = ListNode(sums % 10)
l1 = l1.next
l2 = l2.next

node = res
while l1 and l2:
sums = l1.val + l2.val + carry
tmp = ListNode(sums % 10)
carry = sums / 10

node.next = tmp
node = node.next
l1 = l1.next
l2 = l2.next

while l1:
sums = l1.val + carry
tmp = ListNode(sums % 10)
carry = sums / 10

node.next = tmp
node = node.next
l1 = l1.next

while l2:
sums = l2.val + carry
tmp = ListNode(sums % 10)
carry = sums / 10

node.next = tmp
node = node.next
l2 = l2.next

while carry:
tmp = ListNode(carry % 10)
carry = carry / 10

node.next = tmp
node = node.next

return res

第二版答案

第一版答案中的代码不够精炼,从以下两个地方入手:

  1. 入参判断,对l1和l2的检查上,先定义一个头节点,返回头节点的next,这样可以避免处理l1或l2为空的情形,将链表中所有的节点一视同仁进行处理;
  2. 将四个while语句合并处理

代码如下:

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
# 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
"""
head = ListNode(0)

carry = 0
node = head
while l1 or l2 or carry:
val1, val2 = 0, 0
if l1:
val1 = l1.val
l1 = l1.next

if l2:
val2 = l2.val
l2 = l2.next

sums = val1 + val2 + carry
tmp = ListNode(sums % 10)
carry = sums / 10

node.next = tmp
node = node.next

return head.next

代码简洁了许多,由于增加了比较多的比较,效率会稍微下降点。

0%