本文共 2603 字，大约阅读时间需要 8 分钟。

singly-linked-list: 模拟数字加法

在现实的编程练习中，我们有时会遇到需要通过模拟手动加法来完成算法实现的情况。这种方法通常用于处理类似数字相加的问题，尤其是在编写测试用例或练习数据操作时特别实用。以下，我将详细介绍如何使用singly-linked list（单向链表）的方式来模拟数字的加法，并处理可能的进位问题。

模拟数字加法的逻辑

输入

我们的输入是两个由数字节点组成的链表，每个节点包含一个数字值，还有一个指向下一个节点的指针。需要注意的是，这些节点的数字是按逆序存储的。例如，数字42被表示为2 -> 4，也就是4节点指向2节点。

制作链表

比如，输入：

(2 -> 4 -> 3) + (5 -> 6 -> 4)

我们可以创建以下链表结构：

• 链表A：3 -> 2 -> 4
• 链表B：4 -> 6 -> 5

加法过程

我们可以从链表的第一个节点（末尾）开始加起来，每一步计算当前节点的值之和，再处理可能的进位。具体步骤如下：

完整的加法逻辑

class Solution {
public:
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        if (l1 == NULL && l2 == NULL) return NULL;
        ListNode *head = NULL;
        ListNode *pre = NULL;
        int carry = 0;
        while (l1 && l2) {
            int sum = l1->val + l2->val + carry;
            carry = sum / 10;
            int val = sum % 10;
            ListNode *node = new ListNode(val);
            if (head == NULL) {
                head = node;
            } else {
                pre->next = node;
            }
            pre = node;
            l1 = l1->next;
            l2 = l2->next;
        }
        // 处理可能剩下的节点
        while (l1) {
            int sum = l1->val + carry;
            carry = sum / 10;
            int val = sum % 10;
            ListNode *node = new ListNode(val);
            if (head == NULL) {
                head = node;
            } else {
                pre->next = node;
            }
            pre = node;
            l1 = l1->next;
        }
        while (l2) {
            int sum = l2->val + carry;
            carry = sum / 10;
            int val = sum % 10;
            ListNode *node = new ListNode(val);
            if (head == NULL) {
                head = node;
            } else {
                pre->next = node;
            }
            pre = node;
            l2 = l2->next;
        }
        // 处理最后的进位
        if (carry > 0) {
            ListNode *node = new ListNode(carry);
            if (head == NULL) {
                head = node;
            } else {
                pre->next = node;
            }
        }
        return head;
    }
}

总结

通过上述算法，我们完整地完成了两个单向链表的加法操作，包括处理进位等问题。这种方法能够确保我们能正确地将两个数字相加，并以链表的形式返回结果。

操作流程总结

这种方法确保了我们能够正确地将两个数字相加，并返回合并后的结果。

转载地址：http://jogyk.baihongyu.com/