2. 给定两个非空链表代表两个非负数。这两个非负数是在链表中是按照倒序的方式存储的，每个节点存储了一位数。返回一个链表代表两个非负数相加的和。除了0之外，非负数开头不能是0。 Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { } };

这是一道链表的经典题目，我们可以利用链表的特性从低位到高位进行相加，并且需要注意进位的情况。具体实现可以按照以下步骤：

1. 定义一个进位标记carry，初始值为0，表示没有进位。
2. 定义一个头结点dummy，用于最后返回结果。
3. 定义一个指针cur，初始指向dummy。
4. 循环遍历l1和l2，直到两个链表均为空。
- 在循环中，定义两个变量x和y分别表示l1和l2当前节点的值。
- 计算当前位的和sum = x + y + carry，更新进位carry = sum / 10。
- 创建一个新节点node，其值为sum % 10，将此节点插入到cur之后。
- 将cur指向新插入的节点node。
- l1和l2均非空时，分别将l1和l2指向下一个节点，否则将其指向空节点。
5. 最后检查是否还有进位，若有，则创建一个值为carry的新节点插入到cur之后。
6. 返回dummy的下一个节点即为结果。

以下是具体的实现代码：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0); // 头结点
        ListNode* cur = dummy; // 当前指针
        int carry = 0; // 进位标记
        while (l1 != nullptr || l2 != nullptr) {
            int x = l1 != nullptr ? l1->val : 0;
            int y = l2 != nullptr ? l2->val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1 != nullptr) l1 = l1->next;
            if (l2 != nullptr) l2 = l2->next;
        }
        if (carry > 0) {
            cur->next = new ListNode(carry);
        }
        return dummy->next;
    }
};