C++ 实现两数相加 - 链表解法

class Solution {\npublic:\n ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {\n ListNode *head = nullptr, *tail = nullptr;\n int carry = 0;\n while (l1 || l2) {\n int n1 = l1 ? l1->val: 0;\n int n2 = l2 ? l2->val: 0;\n int sum = n1 + n2 + carry;\n if (!head) {\n head = tail = new ListNode(sum % 10);\n } else {\n tail->next = new ListNode(sum % 10);\n tail = tail->next;\n }\n carry = sum / 10;\n if (l1) {\n l1 = l1->next;\n }\n if (l2) {\n l2 = l2->next;\n }\n }\n if (carry > 0) {\n tail->next = new ListNode(carry);\n }\n return head;\n }}\n这段代码是一个解决两数相加的问题的函数。函数的输入是两个链表，代表两个非负整数，链表的每个节点代表整数的一位，且节点的值范围是0-9。函数的输出是一个新的链表，代表两个输入链表所代表的整数的和。\n\n函数的实现思路是使用一个循环来遍历两个输入链表，同时对应位置上的节点值相加，并加上进位值。如果有进位，则进位值为1，否则为0。将相加的结果取余数得到新链表节点的值，将相加的结果除以10得到进位值。然后将新节点添加到新链表中。\n\n循环结束后，如果还有进位值，则需要在新链表的末尾再添加一个节点，节点的值为进位值。\n\n最后返回新链表的头节点。\n\n整个过程中，使用了两个指针head和tail来记录新链表的头节点和尾节点，方便添加新节点。同时使用了一个变量carry来记录进位值。\n\n这段代码的时间复杂度是O(max(m,n))，其中m和n分别是两个输入链表的长度。