将由链表表示的两个数字相加

题目解析

本题要求实现将由链表表示的两个数字相加。链表是一种数据结构,通常用于存储一系列元素,相比于数组,链表的插入和删除操作更加高效。而链表相加就是按照从低位到高位的顺序将对应位置的数字相加并进位,最后得到结果。

解题思路

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;

}

};

免责声明:本文来自互联网,本站所有信息(包括但不限于文字、视频、音频、数据及图表),不保证该信息的准确性、真实性、完整性、有效性、及时性、原创性等,版权归属于原作者,如无意侵犯媒体或个人知识产权,请来电或致函告之,本站将在第一时间处理。猿码集站发布此文目的在于促进信息交流,此文观点与本站立场无关,不承担任何责任。

后端开发标签