在上一篇两数之和中，我们学会了利用哈希表加速无序数组中的查找，，但算法世界中的“加法”远不止一种数据结构。本次将焦点切换到链表这一线性结构。

回答的核心问题是：如何在不将链表转换为整型数字（避免溢出）的前提下，模拟两个逆序存储的链表所代表的数字相加，并输出同样逆序的结果链表？

题目：

image

链表节点（ListNode）

链表是由一系列节点通过指针串联而成，每个节点包括两个部分。

  • val：当前节点存储的数字。
  • next：指向下一个节点的指针。

链表节点是构建所有链表操作的基础。理解 val 和 next 的语义，是后续模拟加法的前提。

链表节点是数据结构中最基础的单元之一，节点本身不存储链表长度，需遍历获取，next指针为null表示链表结束，链表节点与数组元素不同，它在内存中不连续，通过指针链接，因此插入和删除操作效率更高。

容易混淆 val 和 next 的赋值操作。例如 node.next = node 会导致自环，形成无限循环，这是链表操作中的常见错误。务必确保 next 指向的是另一个节点或 null，而不是自身。

逐位加法与进位：模拟手工加法

如何模拟手工加法呢？经历下面四个步骤即可。

image

核心算法逻辑如下：

模拟手工加法，从低位到高位逐位相加，并处理进位。

  • 当前位：使用%运算提取个位数字。
  • 进位：使用/运算提取十位数字（进位值）。
  • 迭代：同时移动两个链表指针，直到两者都为空且无进位。

边界情况

image

容易忽略最后一位的进位。例如 5 + 5 = 10，结果链表应为 0 → 1，但若循环条件只检查 l1 != null || l2 != null，则会漏掉最后的进位 1，导致结果错误。必须将 carry != 0 加入循环条件。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 dummy,*tail=&dummy;
        int carry=0;
        while(l1 || l2 ||carry)
        {
            int sum=carry+(l1?l1->val:0)+(l2?l2->val:0);
            carry=sum/10;
            tail->next=new ListNode(sum%10);
            tail=tail->next;
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        return dummy.next;
    }
};

趣味评论小剧场

通过自己不断学习算法，终于入职了美团，大厂就是不一样，站长人很好，送我衣服，头盔，还有电动车电池。