题目:
1 | 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. |
实际上就是用一个按倒叙存储的链表实现两个整数的加法并返回一个链表。
分析
我们先来看一下如何用Python实现一个链表:1
2
3
4
5class 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 | def addTwoNumbers(l1,l2): |
carry是进位数。
在python中,可以将1
2n.next = ListNode(val)
n = n.next
缩写成1
n.next = n = ListNode(val)
所以最后的代码可以精简为:1
2
3
4
5
6
7
8
9
10
11
12
13def 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