首页 > 其他分享 >力扣第二题——两数相加(链表的讲解与运用,含解决链表问题模板)(含思路详解、完整代码与知识点精炼)

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

时间:2024-07-23 15:27:03浏览次数:15  
标签:知识点 ListNode struct next 链表 力扣 tail l1

内容介绍

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

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

你可以假设除了数字 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 的当前值是 9l2 的当前值是 9
    • sum = 9 + 9 + 0 = 18
    • carry = 18 / 10 = 1
    • 创建新节点,其值为 sum % 10 = 8
    • head 和 tail 都指向这个新节点。
  3. 第二次循环:

    • l1 的当前值是 9l2 的当前值是 9
    • sum = 9 + 9 + 1 = 19
    • carry = 19 / 10 = 1
    • 创建新节点,其值为 sum % 10 = 9
    • 将新节点添加到链表末尾,更新 tail
  4. 第三次循环:

    • l1 的当前值是 9l2 的当前值是 9
    • sum = 9 + 9 + 1 = 19
    • carry = 19 / 10 = 1
    • 创建新节点,其值为 sum % 10 = 9
    • 将新节点添加到链表末尾,更新 tail
  5. 第四次循环:

    • l1 的当前值是 9l2 的当前值是 9
    • sum = 9 + 9 + 1 = 19
    • carry = 19 / 10 = 1
    • 创建新节点,其值为 sum % 10 = 9
    • 将新节点添加到链表末尾,更新 tail
  6. 第五次循环:

    • l1 的当前值是 9l2 的当前值是 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 函数遍历链表并打印每个节点的值。

总结

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

标签:知识点,ListNode,struct,next,链表,力扣,tail,l1
From: https://blog.csdn.net/m0_74932528/article/details/140546266

相关文章

  • 力扣209. 长度最小的子数组C++、窗口写法
    给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl,numsl+1,...,numsr-1,numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。示例1:输入:target=7,nums=[2,3,1,2,4,3]......
  • 力扣68. 文本左右对齐
    给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 '' 填充,使得每行恰好有 maxWidth 个字符。要......
  • 力扣题库合集(2):动态规划(1)
      本文将持续更新~~ hellohello~,这里是绝命Coding——老白~......
  • 数据结构-线性表(单链表)
    线性表-链表顺序表的链式表示顺序表和链表链表链表实现初始化相关操作插入顺序表的链式表示顺序表和链表顺序表可以随机存取表中的任意元素,但插入和删除操作需要移动大量元素。链表不需要使用地址连续的存储单元,即不需要逻辑上相邻的元素在物理位置上也相邻,通......
  • Python入门知识点 5--流程控制语句
    先来分享一个pycharm使用小技巧   红色波浪线:提醒可能报错   黄色波浪线:提醒书写不规范,ctrl+alt+l去掉黄线   code--Reformatcode,就可以去掉黄线,调整代码格式1、程序三大执行流程(1)顺序执行        程序执行时,代码从上往下,从左往右执行,中间......
  • C语言指针易混淆知识点总结
    指针定义指针是一个变量,存储另一个变量的内存地址,它允许直接访问和操作内存中的数据,使得程序能够以更灵活和高效的方式处理数据和内存。获取变量地址:使用取地址符&。访问地址上的数据:使用解引用符*。例子1指针是存储另一个变量地址的变量。通过使用取地址符&和解引用符......
  • 7/22 课堂知识点总结
    斐波那契数列解法用数组来一个一个寸为什么不用递归?递归层数太多,容易爆栈系统栈:2mb一般的递归层数:2*\(10^4\)//正常解法for(inti=3;i<=n;i++)a[i]=a[i-1]+a[i-2];时间复杂度:O(n).//递归解法intf(intx){if(x==1||x==2)re......
  • 反转链表
    注意:反转结束后,从原来的链表上看,\(pre\)指向反转这一段的末尾,\(cur\)指向反转这一段后续的下一个节点。206.反转链表/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}......
  • 力扣LCR 039. 柱状图中最大的矩形
    思路用到了单调栈。由于最大矩形它的高一定是height数组中的其中一个值,那么我们就可以遍历数组height的值再乘上它的宽的最大值WidthMax(宽的最大值后面会讲),然后取最大值就是答案,也就是ans=max(ans,WidthMax*height[x])。那么如何求高为height[x]的宽的最大值WidthMax呢?解题过程......
  • 【数据结构】:链表实现洗牌功能
    此操作包含的基本功能有:组牌:组建52张扑克牌四种花色:“♥️”,“♠️”,“⬛️”,“♣️”每种花色13张牌:1~13洗牌:将52张扑克牌打乱顺序发牌:给三个人每人发5张牌扩展功能:清牌:将每人手中牌按照面值进行从大到小排序Card类在此类中,我们将完成对每一张牌的构造类......