2 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.
Example 1:
Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Note:
- You may assume the two numbers do not contain any leading zero, except the number 0 itself.
题目翻译
给定两个链表，非负元素从低位向高位排列，如(2 -> 4 -> 3)表示342。求两个链表对应数据之和并从低位到高位输出。
示例1：
输入： (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
注意：
- 除链表对应数据为零外，数据首位元素不为零
解题方案
标签： Array
思路：
- 模拟十进制加法运算，从低位到高位两个链表l1,l2公共部分依次相加求和，链表l3为对应两个元素的和，等于本位相加再加上进位。
- 当本位之和加进位大于10时，进位为1，保留本位之和加进位减去10作为l3本位。否则，进位为零，本位之和加进位作为l3的本位
- 最后对于两个链表中长的那一个，将最低位加上进位继续求和后链接到l3后面作为输出即可。
代码：
# 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
"""
l3, p1, p2= ListNode(0), l1, l2 #l3为新链表头结点
temp = l3 #当前和前一个元素指针(不设temp=l3.next，防止赋空值出现错误)
carry = 0 #进位
while p1 and p2: #遍历两个链表公共部分
num = p1.val + p2.val + carry
if num > 9:
num -= 10
carry = 1 #和大于10，进位为1
else:
carry = 0 #和小于10，进位为0
# 尾插法添加结点
temp.next = ListNode(num)
temp = temp.next
# 向后移动l1,l2工作指针
p1 = p1.next
p2 = p2.next
#END WHILE
# 取两条链长的那条剩下的部分
if p2: p1 = p2
#对长的链表继续求和
while p1:
num = p1.val + carry #加上进位
if (num > 9):
num -= 10
carry = 1
else:
carry = 0
#尾插法添加新节点
temp.next = ListNode(num)
temp = temp.next
#向后移动工作指针
p1 = p1.next
# 如果最后还有进位，再分配一个结点，值为1
if carry:
temp.next = ListNode(1)
temp = temp.next
temp.next = None # 将链表收尾
return l3.next #去掉空的头结点