2. 两数相加

题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

样例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

解释 : 342 + 465 = 807

算法 模拟($O(n)$)

思路

遍历两个链表，对应数字的每一位相加。

如果对应的节点存在，改位就取其值，不存在认为改位为0。

• 以相加后sum对10取模的值(sum % 10)，生成新的节点
• 同时更新新的进位值

细节

• 注意最后一位的进位

复杂度

• 时间 ： $O(n)$
• 空间 ： $O(1)$

c++ 代码

leetcode版本

/**
 * 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 *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        int carry = 0;

        while(l1 || l2)
        {
            int n1 = l1 ? l1 -> val : 0;
            int n2 = l2 ? l2 -> val : 0;
            int sum = n1 + n2 + carry;
            cur -> next = new ListNode(sum % 10);
            carry = sum / 10;
            cur = cur -> next;
            if(l1) l1 = l1 -> next;
            if(l2) l2 = l2 -> next;
        }
        if(carry) cur -> next = new ListNode(1);

        return dummy -> next;
    }
};

本地版本

#include <iostream>

using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr){}
};
// 将数字转化为链表 逆序存储
ListNode* nums2List(int x)
{
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;
    while(x) {
        cur->next = new ListNode(x % 10);
        cur = cur->next;
        x /= 10;
    }
    return dummy -> next;
}
// 打印链表
void printList(ListNode *node)
{
    while(node){
        cout << node -> val << " -> " ;
        node = node -> next;
    }
    cout << "NULL" << endl;
}
// 链表对应位相加
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *dummy = new ListNode(-1); 
    ListNode *cur = dummy;
    int carry = 0;

    while(l1 || l2)
    {
        int n1 = l1 ? l1 -> val : 0;
        int n2 = l2 ? l2 -> val : 0;
        int sum = n1 + n2 + carry;
        cur -> next = new ListNode(sum % 10);
        carry = sum / 10;
        cur = cur -> next;
        if(l1) l1 = l1 -> next;
        if(l2) l2 = l2 -> next;
    }
    if(carry) cur -> next = new ListNode(1);

    return dummy -> next;
}

int main()
{
    int a, b;
    cin >> a >> b;

    ListNode *pHead_A = nums2List(a);
    ListNode *pHead_B = nums2List(b);
    ListNode *addHead = addTwoNumbers(pHead_A, pHead_B);

    printf("数字a = %d, 其转换为链表的结果为：\n", a);
    printList(pHead_A);
    printf("数字b = %d, 其转换为链表的结果为：\n", b);
    printList(pHead_B);
    printf("相加结果为：\n");
    printList(addHead);

    return 0;
}

/*
Input:
342 465

Output:
数字a = 342, 其转换为链表的结果为：
2 -> 4 -> 3 -> NULL
数字b = 465, 其转换为链表的结果为：
5 -> 6 -> 4 -> NULL
相加结果为：
7 -> 0 -> 8 -> NULL 
*/

小结与思考

• 链表的尾插法练习

• 进阶：实现链表的相关操作

  • ListNode 结构体 版本

  • 数组模拟单链表版本 如 AcWing 826. 单链表

    #include <iostream>

    using namespace std;

    const int N = 100010;


    // head   头节点的下标
    // e[i]   节点i的值
    // ne[i]  节点i的next指针是多少
    // idx    存储当前已经用到了哪个点  目前可用的
    // 静待链表
    int head, e[N], ne[N], idx;

    // 初始化
    void init()
    {
        head = -1; // head 指向空
        idx = 0;
    }
    // 将x插入到头结点 头插
    void add_to_head(int x)
    {
        e[idx] = x;
        ne[idx] = head;  // idx 指向 head 指向的东西 
        head = idx;  // head 指向 idx
        idx ++;
    }
    // 将x插到到小标为k的结点后面
    void add(int k, int x)
    {
        e[idx] = x;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx ++;
    }
    // 将下标为K后面的点删除
    void remove(int k)
    {
        ne[k] = ne[ne[k]];
    }

    int main()
    {
        int m;
        cin >> m;

        init();

        while(m --)
        {
            int k ,x;
            char op;

            cin >> op;
            if(op == 'H')
            {
                cin >> x;
                add_to_head(x);
            }
            else if(op == 'D')
            {
                cin >> k ;
                if(!k) head = ne[head]; // 对删除头结点特判
                remove(k - 1);
            }
            else 
            {
                cin >> k >> x;
                add(k -1 , x);
            }
        }

        for(int i = head; i != -1; i = ne[i])
            cout << e[i] << ' ';

        return 0;
    }

    // 第k个插入的点的下标 是 k-1