题目：

leetcode2题目描述

解法：

对两个链表分别设置一个指针，构造一个新的链表用于存储当前两个节点之和的值，当前节点被遍历过后，指针后移。对于满10进位时，设置一个进位判断。
首先，我们构建一个值位0的头结点，并将其存为pHead，从下一个节点开始才存储最终要返回结果的个位、十位、百位......
$l1$ 和 $l2$ 会出现链表长短不一样的情况，所以进入while循环后，我们首先判断 $l1$ 或 $l2$ 当前指针所指的节点是否有值，如果有我们就将其加入sum中。当前位就是sum(l1.val+l2.val+flag)对10取余，并将该节点插入pNode节点后，进位就是sum(l1.val+l2.val+flag)除以10后取整。执行完前面操作后，向后移动指针，继续执行。
有一种特殊情况，遍历完 $l1$ 和 $l2$ 后有进位，比如5+5=10，所以要在while循环外检查一下flag值，确定上一位是否进位了，如果有进位，将进位加入到链表尾。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        pNode = ListNode(0)
        pHead = pNode
        flag = 0
        while l1 or l2:
            sum = 0
            if l1 is not None:
                sum = sum + l1.val
                l1 = l1.next
            if l2 is not None:
                sum = sum + l2.val
                l2 = l2.next
            
            sum = sum + flag
            flag = int(sum / 10)
            pNode.next = ListNode(sum%10)
            pNode = pNode.next
        if flag == 1:
            pNode.next = ListNode(1)
        return pHead.next

复杂度分析：