当前位置:   article > 正文

LeetCode算法学习——链表_struct node* list = null;

struct node* list = null;

链表的顺序插入

链表的数据结构

最基本的单向链表:就是一个存放了数据和下一个节点地址的结构体

struct Node{
	int data;             //存放数据
	struct Node* next;    //next是用于指向下一个节点的地址
};
  • 1
  • 2
  • 3
  • 4
链表的创建及赋值
struct Node *list = NULL;      //创建一个链表变量
list = (struct Node*)malloc(sizeof(struct Node));      //分配地址
list->data = 1;
list->next = NULL;
  • 1
  • 2
  • 3
  • 4

创建链表list变量的时候需要初始化为空,此时该变量还未获得地址空间,需要动态给list分配内存,然后给list->data赋值。
list->next = NULL;设置为空是重点,这个必须加上,不然list->next会随机有一个值(就像我们声明一个变量的时候,没有给变量初始化,这个变量是会有一个随机的数的),这个值就是下一个节点的地址,下一个节点里面的内容都是随机的,那么下一个节点所指向的下一个节点的地址也是随机的一个值,即list->next->next也是一个随机的地址,这样就会一直随机地指向下一个节点,无穷无尽。
基于链表的特性给链表的赋值操作是:

1、第一种赋值方式

struct Node *List = NULL;     //创建一个链表变量	初始化为空
List = (struct Node*)malloc(sizeof(struct Node));            //分配内存 
List->data = 0;              //给数据赋值
//List->next = NULL;         //如果使用这个语句,那么这里就可以完成给链表第一个节点的赋值   下面的操作是给链表下一个节点赋值
List->next = (struct Node*)malloc(sizeof(struct Node));      //为一下个节点分配内存   
List = List->next;           //链表的第一个节点更新,将下一给节点作为首节点,那么开始的时候的第一个节点的数据将会丢失
List->data = 1;              //给节点赋值
List->next = (struct Node*)malloc(sizeof(struct Node));      //给下一个节点分配内存
List = List->next;           //更新首节点位置,依然是将下一个节点作为首节点,前面节点的数据将会丢失
List->data = 2;              //给节点赋值
List->next = NULL;           //结束,需要将指向下一个节点的地址赋空值,否则链表将会随机指向无穷远
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

在上面的代码可以看出,使用这种方式给节点赋值将会对整个链表毫无意义,每当我们给下一个节点赋值的时候,上一个节点的数据将会丢失。
2、第二种赋值方式

struct Node *List = NULL;       //创建一个链表变量	初始化为空
List = (struct Node*)malloc(sizeof(struct Node));            //分配内存 
List->data = 0;                 //给数据赋值
List->next = (struct Node*)malloc(sizeof(struct Node));      //为一下个节点分配内存   
List->next->data = 1;           //给下一个节点的数据位赋值,第一个节点数据不会丢失
List->next->next = (struct Node*)malloc(sizeof(struct Node));      //给下一个节点的下一个节点分配内存
List->next->next->data = 2;     //给下一个节点的下一个节点的数据位赋值
List->next->next->next = NULL;  //结束
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

使用这种方式给链表赋值不会造成数据的丢失,但缺点很明显。如果需要给第十个节点赋值那就麻烦了。
所以我们需要一种新的赋值方式。

链表插入需要创建两个链表变量:
// 第一步:创建两个链表
struct Node *head = NULL, *List = NULL;      //创建两个链表变量 初始化为空
head = List = (struct Node*)malloc(sizeof(struct Node));      
	//list和List所指向的首个节点地址一样(注意:这两个链表是指针变量,它们共同指向一个地址空间。),
	//但它们的地址不一样,指针的知识,不懂的可以补补知识哦。即两个指针变量所存储的地址是一样的,
	//都是指向首个节点的地址。现在它们所存放的首个地址是一样的,经过第二步就不一样了。
List->data = 0;          //给List所指向的第一个节点的数据位赋值,又因为它们指向的节点一样,
	//所以head的首个节点的数据位也被赋值0
//第二步
List->next = (struct Node*)malloc(sizeof(struct Node));  //给List的下一个节点开辟地址空间,
	//head也是一样,它们首个节点所指向的下一个节点是一样的
List = List->next;   //现在List所指向的首个节点的地址开始发生变化了,指向了原来首个节点的下一个节点了,
	//即List指针变量存放指向首个节点的地址发生变化了,head和List指针变量存放的地址不一样了。
List->data = 1;
//第三步
List->next = (struct Node*)malloc(sizeof(struct Node));
List = List->next;
List->data = 2;
List->next = NULL;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

下面是我画的两张节点插入流程图,不知道有没有朋友可以看懂,可能过久一点我自己都看不懂了哈哈哈。
第一张流程图应该合理、容易明白一些,第二张图给自己以后看的,能看懂第一章就行。
第一种

第二种

总结

struct Node *list = NULL; 创建了一个指针变量,这个list指针变量存放了指向首个节点的地址。
当需要创建一个完整的多节点链表的时候,需要创建两个链表指针变量配合使用。
开始两个链表指针变量head和list指向同一个节点,然后head链表指针变量存放的首个节点的地址不改变,list不断更变链表指针变量指向的节点地址,list每次都是指向新节点的地址(list原来首个节点的数据丢失),但head链表的节点不断变长,且数据得到保留。

清楚这些问题后,我们来学习一下LeetCode算法的第二题,肯定会得心应手了。

LeetCode题库第二题:两数相加

题目:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers

/**
 * 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, *mid = NULL; //创建两个链表并初始化为空 head作为不变的链表,用于存放数据
                                               //mid作为移动的链表
    int count = 0;            //记录进位
    while(l1 || l2){          //判断两个链表是否都为空,都为空结束计算
        int x = l1 ? l1->val : 0;     
        int y = l2 ? l2->val : 0;       //取值
        int sum = x + y + count;        //对应为以及前一位的进位数相加
        if(head==NULL){                 //head链表是否为空
            head = mid = (struct ListNode*)malloc(sizeof (struct ListNode));   //分配共同的首节点地址
            mid->val = sum%10;          //赋值,存放个位数
            mid->next = NULL;           //所指向的下一个节点为空
        }     
        else{
            mid->next = (struct ListNode*)malloc(sizeof(struct ListNode));  //为下一个节点分配内存
            mid = mid->next;            //mid移动都下一个节点
            mid->val = sum%10;          //赋值
            mid->next = NULL;           //所指向的下一个节点为空
        }
        count = sum/10;                 //计算进位 
        if(l1) l1 = l1->next;           
        if(l2) l2 = l2->next;           //两个链表不为空的时候更新,使他们指向下一个节点
    }
    if(count){                          //前面结束后判断是否有进位,如果有进位则需要再开辟一个节点用于存放
        mid->next = (struct ListNode*)malloc(sizeof(struct ListNode));   //为下一个节点分配内存
        mid->next->val = count;         //为mid的下一个节点赋值
        mid->next->next = NULL;         //下一个节点的下一个节点指向为空
    }
    return head;           //返回地址不变的链表
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

基本思路:
1、先判断是否开辟了空间,未开辟空间(即head和mid链表指针变量里面存放的地址还没有指向一个节点),那么需要开辟空间,即让head和mid链表指针变量里面存放的地址是首个一个节点。然后赋值,指向下一个节点的地址为空。
2、已经开辟首节点空间,那么就先给下一个节点开辟空间,然后mid移动都下一个节点(即mid链表指针变量存放的地址变为下一个节点的地址),然后给节点数据赋值,下一个节点地址设置为空。(也可以先给下一个节点开辟空间,然后给下一个节点数据赋值,再讲mid移动到下一个节点,官方的答案就是这样的,好像这样的方法运行速度会快一点)。
3、最后判断是否还有进位(最后while结束count的数值可能不为零,即还有一个进位,并且还没存放到链表中),因此需要再开辟一个节点存放进位。

单向链表学习结束。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/618151
推荐阅读
相关标签
  

闽ICP备14008679号