题目解析
本题要求实现将由链表表示的两个数字相加。链表是一种数据结构,通常用于存储一系列元素,相比于数组,链表的插入和删除操作更加高效。而链表相加就是按照从低位到高位的顺序将对应位置的数字相加并进位,最后得到结果。
解题思路
1. 初始化
首先设定一个carry变量,其表示进位。同时设定一个新的位于0号位置的头结点dummyHead节点,其next为第一个节点。
ListNode* dummyHead = new ListNode(0);
ListNode* p = l1, *q = l2, *curr = dummyHead;
int carry = 0;
2. 遍历相加
然后在while循环中遍历l1和l2的每一位数字,在遍历中进行相加,并且将carry的值相应地更新。
while (p != nullptr || q != nullptr) {
int x = (p != nullptr) ? p->val : 0;
int y = (q != nullptr) ? q->val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (p != nullptr) p = p->next;
if (q != nullptr) q = q->next;
}
3. 处理进位
在while循环中完成之后,如果carry的值为1,则表示还有一个进位,需要额外再创建一个节点来表示。
if (carry > 0) {
curr->next = new ListNode(carry);
}
4. 返回结果
最后返回dummyHead的next,即为结果。
return dummyHead->next;
完整代码
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(0);
ListNode* p = l1, *q = l2, *curr = dummyHead;
int carry = 0;
while (p != nullptr || q != nullptr) {
int x = (p != nullptr) ? p->val : 0;
int y = (q != nullptr) ? q->val : 0;
int sum = carry + x + y;
carry = sum / 10;
curr->next = new ListNode(sum % 10);
curr = curr->next;
if (p != nullptr) p = p->next;
if (q != nullptr) q = q->next;
}
if (carry > 0) {
curr->next = new ListNode(carry);
}
return dummyHead->next;
}
};