C++程序 链表表示的两个数字相加-第1部分

介绍

在这篇文章中，我们将探究用链表表示的两个数字相加。这是一个经典的面试算法问题，很多公司都会在面试中提到这个问题。尤其是在计算机科学和软件开发领域，这是一个非常常见的问题。

问题

问题描述如下：假设有两个用链表表示的整数，每个节点中的值代表一个数字的一位。这两个整数必须相加并返回一个用链表表示的新整数。

示例代码

下面是一个示例代码，如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = NULL, *tail = NULL;
        int carry = 0;
        while (l1 != NULL || l2 != NULL) {
            int n1 = l1 != NULL ? l1->val : 0;
            int n2 = l2 != NULL ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (head == NULL) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1 != NULL) l1 = l1->next;
            if (l2 != NULL) l2 = l2->next;
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

上述代码的主要思路是遍历两个链表，同时按位进行相加，并保留进位。同时，我们需要维护一个新的链表来存储结果。

代码解析

现在，我们一步一步地来解析上述代码的内容。

定义两个链表

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

此处，我们定义了两个链表 l1 和 l2，表示我们需要相加的两个数字。

定义新链表

ListNode *head = NULL, *tail = NULL;

这里，我们定义了一个新链表 head 和 tail，用于存储结果。head指向整个链表的头部，而tail则指向链表尾部的节点。

遍历链表

while (l1 != NULL || l2 != NULL) {

遍历两个链表 l1 和 l2，若两个链表中有任意一个没有遍历完，则继续循环。

求每一位的和

int n1 = l1 != NULL ? l1->val : 0;
int n2 = l2 != NULL ? l2->val : 0;
int sum = n1 + n2 + carry;

在每一次循环中，我们需要计算每一位的和，包括进位。

存储结果

if (head == NULL) {
    head = tail = new ListNode(sum % 10);
} else {
    tail->next = new ListNode(sum % 10);
    tail = tail->next;
}

根据问题描述中相加的要求，我们需要用一个新链表来存储结果。因此，我们需要判断当前结果链表 head 是否为空，如果为空，则将当前 sum 的个位数作为新链表的头节点，否则，我们需要把新节点连接到链表的尾部。

处理进位

carry = sum / 10;

如果两个链表的相加之和大于10，则需要进位。因此，我们需要将 sum 除以 10 以计算进位值。

遍历下一个节点

if (l1 != NULL) l1 = l1->next;
if (l2 != NULL) l2 = l2->next;

在每次循环中，我们需要遍历链表的下一个节点。

处理最后一个进位

if (carry > 0) {
    tail->next = new ListNode(carry);
}

如果遍历完链表之后，存在进位，则需要在新链表的尾部添加一个新节点。

返回结果

return head;

最后，我们需要返回新的链表 head。

结论

通过上述代码的讲解，我们掌握了如何用链表表示的两个数字相加。这是一个经典的面试算法问题，大家可以在学习完毕之后，尝试着对其进行实现和优化。