当前位置：首页 > news >正文

链表(两数相加)(1)

news 2026/6/9 14:31:29

一.题目

2. 两数相加 - 力扣（LeetCode）

二.思路讲解

2.1 审题

题目给出两个非空链表，每个链表表示一个非负整数，并且数字是逆序存储的，即链表的头节点对应数字的最低位。例如，链表2->4->3表示数字342。我们需要将这两个数相加，并返回一个同样以逆序形式表示和的链表。题目保证除了数字 0 本身，否则不会以 0 开头，这确保了输入是合法的。

2.2 虚拟头节点（哨兵位）

在链表操作中，经常需要处理头节点的特殊情况。例如，当我们依次向结果链表中添加节点时，第一个节点需要被设置为头节点，后续节点则接在尾部。如果不用虚拟头节点，就需要单独判断是否第一个节点，这会使代码变得繁琐。因此，我们引入一个虚拟头节点new_head，它是一个哨兵节点，不存储实际数据，仅作为一个占位符。这样，我们始终将新节点接在head（初始指向虚拟头节点）的后面，然后移动head。最终返回new_head->next即可得到真正的结果链表头。这种方法避免了边界判断，简化了代码逻辑。

2.3 思路讲解

本题的核心是模拟竖式加法，从最低位（链表头）开始逐位相加，并处理进位。具体步骤如下：

初始化两个指针cur1和cur2分别指向两个输入链表的头节点，用于遍历。
创建虚拟头节点new_head，并让指针head也指向它，head将始终指向当前结果链表的末尾。
定义变量t用于存储当前位的和以及进位，初始为 0。

然后进入循环，条件为cur1 != nullptr || cur2 != nullptr，即只要有一个链表还有节点，就继续处理。在循环中：

如果cur1非空，则将其值加到t上，并将cur1移向下一个节点。
如果cur2非空，同样将其值加到t上，并将cur2移向下一个节点。
然后，当前位的和为t % 10，我们创建一个新节点存入该值，并将其接到head->next，然后移动head到新节点。
更新进位t = t / 10，用于下一轮计算。

循环结束后，可能还存在最后的进位（即t不为 0），此时需要再创建一个节点存放该进位值，并接到链表末尾。

最后，返回new_head->next，即结果链表的头节点。

三.代码演示

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* cur1 = l1; ListNode* cur2 = l2; ListNode* new_head = new ListNode; ListNode* head = new_head; int t = 0; while(cur1 != nullptr || cur2 != nullptr) { //判断l1是不是空节点 if(cur1 != nullptr) { t += cur1->val; cur1 = cur1->next; } //判断l2是不是空节点 if(cur2 != nullptr) { t += cur2->val; cur2 = cur2->next; } ListNode* node = new ListNode(t % 10);//取t的个位数作为节点的值 t = t / 10;//进位 head->next = node;//让头节点连接该节点 head = head ->next;//让头节点往前 } if(t != 0) { ListNode* node = new ListNode(t % 10);//取t的个位数作为节点的值 head->next = node;//让头节点连接该节点 } return new_head->next; } };

四.代码讲解

一、初始化遍历指针和虚拟头节点

首先，我们需要两个指针cur1和cur2分别指向输入链表l1和l2的头节点，用于后续遍历。同时，为了简化结果链表的构建，我们创建一个虚拟头节点new_head，它是一个哨兵节点，不存储实际数据。再定义一个指针head也指向这个虚拟头节点，head将始终指向当前结果链表的末尾，方便我们添加新节点。此外，定义一个整型变量t用于存储当前位的和以及进位，初始化为 0。

二、遍历两个链表进行逐位相加

进入while循环，条件为cur1 != nullptr || cur2 != nullptr，即只要两个链表中还有未处理的节点，就继续循环。这样能自动处理两个链表长度不一致的情况。

在循环内部，首先处理两个链表当前节点的值：

如果cur1不为空，则将其值加到t上，并将cur1移向下一个节点。
如果cur2不为空，同样将其值加到t上，并将cur2移向下一个节点。

此时，t中存储的是当前位的和加上来自低位的进位。接着，我们创建新节点，其值为t % 10（即当前位的个位数），并将该节点连接到结果链表中：

将head->next指向这个新节点。
然后将head移动到新节点，即head = head->next，这样head始终指向结果链表的尾部。

最后，更新进位t = t / 10，为下一位的计算做准备。

三、处理最后的进位

当循环结束后，可能还有一个进位未被处理（即t不为 0）。例如，最高位相加后产生进位，此时需要再创建一个新节点，其值为t % 10（实际上t此时就是进位值，可能大于9吗？实际上进位最多为1，因为两个个位数相加最大9+9+1=19，所以t/10最大为1，但为了通用性，我们还是用取模）。然后将这个节点连接到head->next。

四、返回结果链表

最后，返回new_head->next，即虚拟头节点的下一个节点，也就是结果链表的真正头节点。

五、关键细节

虚拟头节点的作用：避免了在插入第一个节点时需要特殊判断是否为空链表，简化了代码逻辑。
长度不一致的处理：通过循环条件cur1 != nullptr || cur2 != nullptr以及在内部分别判断每个指针是否为空，巧妙地处理了链表长度不等的情况。
进位变量t的妙用：t同时存储当前位的和以及进位，每次计算后更新，既简洁又高效。
最后进位的处理：循环结束后必须检查t是否非零，否则会丢失最高位的进位。
节点创建：使用new ListNode(t % 10)动态创建新节点，每个节点只存储一位数字。