力扣第二题——两数相加（链表的讲解与运用，含解决链表问题模板）（含思路详解、完整代码与知识点精炼）

  • 开发
  • 15

内容介绍

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

完整代码

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

思路详解

题目告诉我们很明确这是一个链表的问题，解决这个问题，首先，让我们先梳理一下什么是链表

链表的基本概念

链表是一种常见的基础数据结构，它由一系列节点（Node）组成。每个节点包含两部分：数据域（存储数据）和指针域（存储下一个节点的地址）。链表的最后一个节点的指针域通常指向空（NULL），表示链表的结束。

以下是链表节点的一个简单定义：

struct ListNode {
    int val;         // 数据域，存储节点的值
    struct ListNode *next; // 指针域，指向下一个节点
};

接着让我用一张图带着大家更好理解链表问题，我个人将链表理解为一个环环相扣的链环，头指针储存着这个链环最开始的一个钥匙，通过这个钥匙，我们可以开始读取这个链表的数据，通过钥匙（头指针）访问完头节点后，我们得到我们储存在链表中的第一个数据，但是链表是一个环环相扣的链环，访问完一个数据（data）后，我们还需要想办法寻找第二个数据，这时我们就需要一个新地址来访问下一个数据，这个地址和前面那个数据加在一起构成了一个结点（Node），第一个通过头指针访问的是头节点，之后不断环环相扣的是中间节点，中间节点可以有无数个，当数据储存完全后，最后一个结点前储存的是最后一个数据，储存指针的地方是NULL，让计算机可以知道我们储存的这个链表已经结束完整。

 

代码解释

现在，让我们来解释这段代码，它实现了两个链表表示的数字相加的功能。

  1. 初始化：

    struct ListNode* head=NULL, *tail=NULL;
int carry=0;
    • head 和 tail 分别用于指向新链表的头部和尾部。
    • carry 用于存储进位，初始为0。

  2. 遍历两个链表：

    while(l1||l2)
    • 使用 while 循环遍历两个链表，直到两个链表都为空。

  3. 获取当前节点的值：

    int n1=l1?l1->val:0;
int n2=l2?l2->val:0;
    • 如果链表 l1 或 l2 不为空，则获取其当前节点的值，否则值为0。

  4. 计算和与进位：

    int sum=n1+n2+carry;
carry=sum/10;
    • 计算当前位的和，并更新进位。

  5. 创建新节点：

    if(!head)
{
    head=tail=malloc(sizeof(struct ListNode));
    tail->val=sum%10;
    tail->next=NULL;
}
else
{
    tail->next=malloc(sizeof(struct ListNode));
    tail->next->val=sum%10;
    tail=tail->next;
    tail->next=NULL;
}
    • 如果新链表为空，则创建第一个节点。
    • 否则，在链表尾部添加新节点。

  6. 移动到下一个节点：

    if(l1) l1=l1->next;
if(l2) l2=l2->next;
    • 如果当前链表节点不为空，则移动到下一个节点。

  7. 处理最后的进位：

    if(carry>0)
{
    tail->next=malloc(sizeof(struct ListNode));
    tail->next->val=carry;
    tail->next->next=NULL;
}
    • 如果最后还有进位，则在新链表尾部添加一个新节点。

  8. 返回结果：

    return head;
    • 返回新链表的头部。

 代码运行演示

让我们以题目中最特殊的例子来过一遍我们写的代码

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

  1. 初始化：

    • head 和 tail 是 NULL。
    • carry 是 0。

  2. 第一次循环：

    • l1 的当前值是 9，l2 的当前值是 9。
    • sum = 9 + 9 + 0 = 18。
    • carry = 18 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 8。
    • head 和 tail 都指向这个新节点。

  3. 第二次循环：

    • l1 的当前值是 9，l2 的当前值是 9。
    • sum = 9 + 9 + 1 = 19。
    • carry = 19 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 9。
    • 将新节点添加到链表末尾，更新 tail。

  4. 第三次循环：

    • l1 的当前值是 9，l2 的当前值是 9。
    • sum = 9 + 9 + 1 = 19。
    • carry = 19 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 9。
    • 将新节点添加到链表末尾，更新 tail。

  5. 第四次循环：

    • l1 的当前值是 9，l2 的当前值是 9。
    • sum = 9 + 9 + 1 = 19。
    • carry = 19 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 9。
    • 将新节点添加到链表末尾，更新 tail。

  6. 第五次循环：

    • l1 的当前值是 9，l2 的当前值是 NULL（因为 l2 已经结束）。
    • sum = 9 + 0 + 1 = 10。
    • carry = 10 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 0。
    • 将新节点添加到链表末尾，更新 tail。

  7. 第六次循环：

    • l1 的当前值是 9。
    • sum = 9 + 0 + 1 = 10。
    • carry = 10 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 0。
    • 将新节点添加到链表末尾，更新 tail。

  8. 第七次循环：

    • l1 的当前值是 9。
    • sum = 9 + 0 + 1 = 10。
    • carry = 10 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 0。
    • 将新节点添加到链表末尾，更新 tail。

  9. 第八次循环：

    • l1 的当前值是 9。
    • sum = 9 + 0 + 1 = 10。
    • carry = 10 / 10 = 1。
    • 创建新节点，其值为 sum % 10 = 0。
    • 将新节点添加到链表末尾，更新 tail。

  10. 第九次循环：

    • l1 的当前值是 NULL（因为 l1 已经结束）。
    • sum = 0 + 0 + 1 = 1。
    • carry = 1 / 10 = 0。
    • 创建新节点，其值为 sum % 10 = 1。
    • 将新节点添加到链表末尾，更新 tail。

循环结束，因为 l1 和 l2 都已经为 NULL，且 carry 为 0。

最终，我们得到了链表 [8,9,9,9,0,0,0,1]，即 199999999 。

完整程序

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体定义
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点的函数
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 向链表添加节点的函数
void appendNode(struct ListNode** head, int val) {
    struct ListNode* newNode = createNode(val);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct ListNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 打印链表的函数
void printList(struct ListNode* head) {
    struct ListNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");
}



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


// 主函数
int main() {
    struct ListNode* l1 = NULL;
    struct ListNode* l2 = NULL;
    int n1, n2, val;

    // 输入链表l1的值
    printf("Enter number of elements in list 1: ");
    scanf("%d", &n1);
    printf("Enter elements for list 1: ");
    for (int i = 0; i < n1; i++) {
        scanf("%d", &val);
        appendNode(&l1, val);
    }

    // 输入链表l2的值
    printf("Enter number of elements in list 2: ");
    scanf("%d", &n2);
    printf("Enter elements for list 2: ");
    for (int i = 0; i < n2; i++) {
        scanf("%d", &val);
        appendNode(&l2, val);
    }

    // 打印原始链表
    printf("List 1: ");
    printList(l1);
    printf("List 2: ");
    printList(l2);

    // 计算并打印结果
    struct ListNode* result = addTwoNumbers(l1, l2);
    printf("Result: ");
    printList(result);

    // 释放链表内存
    struct ListNode* temp;
    while (l1 != NULL) {
        temp = l1;
        l1 = l1->next;
        free(temp);
    }
    while (l2 != NULL) {
        temp = l2;
        l2 = l2->next;
        free(temp);
    }
    while (result != NULL) {
        temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

这是一个完整的可运行的程序，我们可以手动输入两个需要相加的L1与L2两个链表，并进行相加，最终会输出答案与每个链表的具象化。

 图例

 

知识点精炼

链表知识点模板

 链表节点结构体定义 

struct ListNode {
    int val;
    struct ListNode *next;
};

创建新节点的函数

struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

向链表添加节点的函数

void appendNode(struct ListNode** head, int val) {
    struct ListNode* newNode = createNode(val);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct ListNode* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

打印链表的函数

void printList(struct ListNode* head) {
    struct ListNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");
}

释放链表内存

struct ListNode* temp;
    while (l1 != NULL) {
        temp = l1;
        l1 = l1->next;
        free(temp);
    }
    while (l2 != NULL) {
        temp = l2;
        l2 = l2->next;
        free(temp);
    }
    while (result != NULL) {
        temp = result;
        result = result->next;
        free(temp);
    }

 ps.这个最后释放内存并不是函数，使用时直接加入主函数的最后就行了

我们解决C语言链表问题时可以直接先写出这些不同功能的函数来解决链表问题，需要用到时可以在主函数中直接调用。

链表的基本操作

  • 创建链表：通过调用 createNode 函数创建新节点，并通过 appendNode 函数将新节点添加到链表末尾。
  • 打印链表：使用 printList 函数遍历链表并打印每个节点的值。

总结

 链表是计算机科学中的一种基础数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。链表在内存中的布局不是连续的，这使得它在某些操作（如插入和删除）上比数组更高效。链表的节点结构体定义、创建新节点的函数、向链表添加节点的函数、打印链表的函数是链表操作的基础模板。这些函数可以作为链表操作的基础模板，根据实际需求可以进一步扩展，例如实现链表的插入、删除、查找等操作。
通过以上我写出的链表模板，当我们多打几遍背熟后就可以快速解决链表问题啦。

阅读全部

相关推荐

  4. 力扣第十题——正则表达式匹配（动态规划化的运用）（附思路讲解、完整代码及知识点精炼）

    2024-07-22 18:08:02       16 阅读

  5. 数据结构链表力扣例题AC（1）——代码以及思路记录（含链表本机调试tips）

    2024-07-22 18:08:02       53 阅读

  7. 【力扣 445】两数相加 II C++题解（链表+模拟+数学+头插法）

    2024-07-22 18:08:02       49 阅读

  9. 【刷题·链表】两数相加

    2024-07-22 18:08:02       62 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 18:08:02       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 18:08:02       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-22 18:08:02       45 阅读

  19. Python语言-面向对象

    2024-07-22 18:08:02       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-22 18:08:02       50 阅读

热门阅读

  6. Blazor Webassembly多标签页实现非iframe的实现

    2024-07-22 18:08:02       17 阅读

  7. MacOS解决安装pycurl的问题 no such file or directory: ‘/usr/lib/libcurl.@libext@‘

    2024-07-22 18:08:02       13 阅读

  9. Lianwei 安全周报|2024.07.22

    2024-07-22 18:08:02       21 阅读

  10. js弹出对话框

    2024-07-22 18:08:02       14 阅读

  16. 优先级策略：在Eureka中配置服务实例优先级

    2024-07-22 18:08:02       20 阅读

  17. L298N的输出电流与电压

    2024-07-22 18:08:02       17 阅读

  19. 基于vite + pnpm monorepo 实现一个UI组件库

    2024-07-22 18:08:02       18 阅读

  22. sqlserver15(2019)修改参数READ_COMMITTED_SNAPSHOT

    2024-07-22 18:08:02       16 阅读

  23. 黑龙江网络安全等级保护测评策略概述

    2024-07-22 18:08:02       13 阅读

  25. Hi3751V351常用命令

    2024-07-22 18:08:02       14 阅读

  27. 鸿蒙笔记--存储

    2024-07-22 18:08:02       15 阅读