两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例 1:
- 输入:l1 = [2,4,3], l2 = [5,6,4]
- 输出:[7,0,8]
- 解释:342 + 465 = 807.
示例 2:
- 输入:l1 = [0], l2 = [0]
- 输出:[0]
示例 3:
- 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
- 输出:[8,9,9,9,0,0,0,1]
示例代码:
# 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
"""
count = 0
ret = ListNode()
tmp = ret
while l1 or l2 or count:
num = 0
if l1:
num += l1.val
l1 = l1.next
if l2:
num += l2.val
l2 = l2.next
if count:
num += count
count -= 1
count, num = divmod(num, 10)
tmp.next = ListNode(num)
tmp = tmp.next
return ret.next
测试代码:
# data structure
class LinkNode(object):
def __init__(self, val):
self.val = val
self.next = None
# create the LinkList
def create_link(link):
if not link:
return
p = head = LinkNode(link[0])
for i in link[1:]:
p.next = LinkNode(i)
p = p.next
return head
# print the link
def print_link(head):
while head:
print(head.val, end=' ')
head = head.next
print()
# 两数相加
class Add(object):
def add(self, x, y):
count = 0
ret = tmp = LinkNode(None)
while x or y or count:
num = 0
if x:
num += x.val
x = x.next
if y:
num += y.val
y = y.next
if count:
num += count
count -= 1
count, num = divmod(num, 10)
tmp.next = LinkNode(num)
tmp = tmp.next
return ret.next
l1 = [9, 2, 7]
l2 = [5, 9, 5]
obj1 = create_link(l1)
obj2 = create_link(l2)
print_link(obj1)
print_link(obj2)
obj = Add()
result = obj.add(obj1, obj2)
print_link(result)
运行结果: