Add Two Numbers

题目:

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
2
3
4
5
class ListNode(object):

def __init__(self, x):
self.val = x
self.next = None

链表的结构其实很简单,只需要一个val和一个指向下一个节点的指针next.

思路

解题思路: 依次遍历两个链表,每次拿出最前的一个节点,将两个val相加,超过10则向后进1,最后将得到的链表返回。

知识点:python中又一个方法可以返回两个数的商和余数:divmod,例如 divmod(12,10) = (1,2)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def addTwoNumbers(l1,l2):

carry = 0
root = n = ListNode(0)
while l1 or l2 or carry:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
carry,val = divmod(v1+v2+carry,10)
n.next = ListNode(val)
n = n.next
return root.next

carry是进位数。

在python中,可以将

1
2
n.next = ListNode(val)
n = n.next

缩写成

1
n.next = n = ListNode(val)

所以最后的代码可以精简为:

1
2
3
4
5
6
7
8
9
10
11
12
13
def addTwoNumbers(l1,l2):
carry = 0
root = n = ListNode(0)
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
carry,val = divmod(carry,10)
n.next = n = ListNode(val)
return root.next

你的支持我的动力