编程实现给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。

算法1：模拟竖式加法

1. 从头节点开始，依次遍历两个链表的节点，将对应位的数字相加，注意进位
2. 如果两个链表长度不同，短的链表的剩余节点的值为0，继续加
3. 如果最高位有进位，需要在链表最后再添加一个节点
4. 返回结果链表

时间复杂度：O(max(m,n))，其中m和n为两个链表的长度

空间复杂度：O(max(m,n))，需要创建新的链表节点来存储结果

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(0); ListNode* cur = res; int carry = 0; while (l1 || l2) { int x = l1 ? l1->val : 0; int y = l2 ? l2->val : 0; int sum = x + y + carry; carry = sum / 10; cur->next = new ListNode(sum % 10); cur = cur->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } if (carry) cur->next = new ListNode(carry); return res->next; } }