Add Two Numbers
题目
https://leetcode.com/problems/add-two-numbers/
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中的链表和使用：
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
l1_1 = ListNode(1)
l1_2 = ListNode(3)
l1_1.next = l1_2
print l1_1.next.val # 3
l1.next == None时为最后一个节点
- 输出整个链表 , print的原型是
print(value, ..., sep=' ', end='\n', file=sys.stdout)因而可以通过调整end来更改输出格式
from __future__ import print_function
def print_list(l):
print(l.val, end=" ")
while l.next is not None:
print("->", end=" ")
print(l.next.val, end=" ")
l = l.next
解题
- 直接做模拟加法，因为是倒序排列，输出也是倒序，所以一位一位的相加即可
from __future__ import print_function
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
"""
temp_val = l1.val + l2.val
l3 = ListNode(temp_val % 10)
start_node = l3
carry = (temp_val / 10)
while l1.next is not None or l2.next is not None:
v1 = l1.next.val if l1.next is not None else 0
v2 = l2.next.val if l2.next is not None else 0
temp_val = v1 + v2 + carry
new_node = ListNode(temp_val % 10)
carry = temp_val / 10
l3.next = new_node
l3 = new_node
if l1.next is not None:
l1 = l1.next
if l2.next is not None:
l2 = l2.next
if carry:
new_node = ListNode(carry)
l3.next = new_node
return start_node
a = Solution()
l1 = ListNode(2)
l1.next = ListNode(4)
# l1.next.next = ListNode(3)
l2 = ListNode(5)
l2.next = ListNode(6)
l2.next.next = ListNode(4)
def print_list(l):
print(l.val, end=" ")
while l.next is not None:
print("->", end=" ")
print(l.next.val, end=" ")
l = l.next
print_list(a.addTwoNumbers(l1, l2))
