2、两数相加

本文主要是介绍2、两数相加，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、问题如下

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

2、思路解析

 在草稿纸上画一画思路还是比较清晰的。第一遍写的时候主要有如下问题：

（1）如何生成全新链表的问题。更准确来说怎么返回链表头。关于这个问题有标准的处理方法：

#定义一个cur指针，后续迭代指针用的都是cur;
#另外定义一个用于返回的root指针,初值就赋予cur;但是最终我们返回的时候返回的是 root->next。
#因为 cur->next 是链表头的首个元素,这也算是通用玩法了。ListNode* cur = new ListNode(0);ListNode* root = p_cur;

（2）另外就是考虑几种特殊情况。例如可能进位的问题、例如链表遍历完毕后如果有进位需要在while循环结束后补一个节点。

 

另外，对着图思路还是比较清晰的，程序代码如下。

#include <iostream>
#include <string>using namespace std;struct ListNode{int val;ListNode* next;ListNode(): val(0), next(nullptr){}ListNode(int v): val(v), next(nullptr){}ListNode(int v, ListNode* n): val(v), next(n){}
};/*
class ListNode{public:int val;ListNode* next;ListNode();ListNode(int v);ListNode(int v, ListNode* n);
};ListNode::ListNode()
{val = 0;next = nullptr;
}ListNode::ListNode(int v){val = v;next = nullptr;
}ListNode::ListNode(int v, ListNode* n){val = v;next = n;
}
*/void print_list(ListNode * l1){ListNode *head = l1;while(head != nullptr){cout << head->val << " ";head = head->next;}cout << endl;
}ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{//ListNode* p_cur(0); //脑子有问题，这些写是个狗屁意思ListNode* p_cur = new ListNode(0);ListNode* lr = p_cur;int add_num = 0; //同位求和数值int gewei = 0;  //记录求和之后的个位数值int shiwei = 0; //记录求和之后的十位数值while(l1 != nullptr || l2 != nullptr){if (l1 != nullptr && l2 != nullptr){add_num = l1->val + l2->val + shiwei;gewei = add_num % 10;shiwei = add_num / 10;p_cur->next = new ListNode(gewei);;l1 = l1->next;l2 = l2->next;p_cur = p_cur->next;//print_list(lr->next);}if (l1 == nullptr && l2 != nullptr){ add_num = l2->val + shiwei;gewei = add_num % 10;shiwei = add_num / 10;p_cur->next = new ListNode(gewei);l2 = l2->next;p_cur = p_cur->next;//print_list(lr->next);}if (l2 == nullptr && l1 != nullptr){add_num = l1->val + shiwei;gewei = add_num % 10;shiwei = add_num /10;p_cur->next = new ListNode(gewei);l1 = l1->next;p_cur = p_cur->next;//print_list(lr->next);}}if (shiwei != 0){p_cur->next = new ListNode(shiwei);}return lr->next;
}int main()
{/*ListNode n11(2);ListNode n12(4);ListNode n13(3);n11.next = &n12;n12.next = &n13;print_list(&n11);ListNode n21(5);ListNode n22(6);ListNode n23(4);n21.next = &n22;n22.next = &n23;print_list(&n21);
*/
/*ListNode n11(9);ListNode n12(9);ListNode n13(9);ListNode n14(9);ListNode n15(9);ListNode n16(9);ListNode n17(9);n11.next = &n12;n12.next = &n13;n13.next = &n14;n14.next = &n15;n15.next = &n16;n16.next = &n17;print_list(&n11);ListNode n21(9);ListNode n22(9);ListNode n23(9);ListNode n24(9);n21.next = &n22;n22.next = &n23;n23.next = &n24;
*/ListNode n11(0);ListNode n21(0);ListNode* result = addTwoNumbers(&n11, &n21);print_list(result);}

 

3、反思

期间犯了一个十分神奇的错误。脑子抽风了。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)

{

        //ListNode* p_cur(0); //脑子有问题，这些写是个狗屁意思

        ListNode* p_cur = new ListNode(0);

        ListNode* lr = p_cur;

        int add_num = 0; //同位求和数值

我们要的是 ListNode 类型的指针 p_cur。

可以这样写：

        ListNode cur(0);

        ListNode* p_cur = &cur;

也可以这样写:

        ListNode* p_cur = new ListNode(0);

明显 “ListNode* p_cur(0);” 啥也不是。脑子抽风了，否则怎么会写出这行代码。

这篇关于2、两数相加的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---