链表中的两数相加C++

链表中的两数相加是一个经典的问题，我们可以通过遍历链表并进行逐位相加来解决。具体的步骤如下：

1. 定义一个新的链表作为结果的头结点，并初始化为空。
2. 定义两个指针分别指向两个链表的头结点，以及一个进位变量carry，初始值为0。
3. 遍历两个链表，直到两个链表都遍历完。
4. 在每个节点上，将两个链表对应位置的值相加，并加上进位值carry。
5. 计算当前位置的值以及进位值，更新结果链表以及进位值。
6. 如果某个链表已经遍历完，但另一个链表还有剩余节点，则将剩余节点的值与进位值相加，并更新结果链表。
7. 如果最后一个节点的相加结果产生了进位，则在结果链表末尾添加一个值为1的新节点。
8. 返回结果链表的头结点。

下面是C++代码实现：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

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

这个算法的时间复杂度是O(max(m, n))，其中m和n分别是两个链表的长度。空间复杂度是O(max(m, n))，用于存储结果链表。