题目描述：

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

解题思路：

首先我们可以用一个标志来记录两条链表中相应元素相加时是否有进位，然后同时遍历两条链表，直到其中一条到达末尾，我们应该注意到，此时可能有一条链表未到达末尾，因此应该对这条链表的未访问元素继续遍历，注意在加时同样要把标志位加上，在两条链表均到达末尾后，判断标志位是否为1，若为1，说明应该在新链表的尾部加上一个值为1的结点。

代码

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ p = ListNode(0) head = p flag = 0 while l1 and l2: p.next = ListNode(l1.val + l2.val + flag) p = p.next flag = 0 l1 = l1.next l2 = l2.next if p.val >= 10: p.val -= 10 flag = 1 while l1: p.next = ListNode(l1.val + flag) flag = 0 l1 = l1.next p = p.next if p.val >= 10: p.val -= 10 flag = 1 while l2: p.next = ListNode(l2.val + flag) flag = 0 l2 = l2.next p = p.next if p.val >= 10: p.val -= 10 flag = 1 if flag: p.next = ListNode(1) return head.next