思路

需要一个新链表来保存结果.

_ 一个阶段还有值
当前总和 = 旧链表中的值和进位值之和
_ 当前保存的值 = (当前总和 % 10)
进位值 = (当前总和 // 10)

cpp 时间复杂度 O(n)

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1), cur = dummy;
        int s = 0;
        while(l1 || l2 || s){
            if(l1) s += l1->val, l1 = l1->next;
            if(l2) s += l2->val, l2 = l2->next;
            cur = cur->next = new ListNode(s % 10);
            s = s/10;
        }
        return dummy->next;
    }
};

python3 O(n)

# 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:
        dummy  = ListNode(-1) # 虚拟头针
        cur = dummy
        s = 0
        while l1 or l2 or s :
            if l1 : 
                s += l1.val
                l1 = l1.next
            if l2 : 
                s += l2.val
                l2 = l2.next
            cur.next = ListNode(s % 10)
            cur  = cur.next
            s = s // 10 # 取模
        return dummy.next