程序员经验分享-hwhale

代码随想录算法训练营第三天 ｜ 203.移除链表元素、707.设计链表、206.反转链表

2023-11-17

目录

知识点：链表

结点定义

单链表的初始化

判断一个链表是否为空

单链表的销毁

清空单链表

求链表表长

取单链表中第i个元素

按值查找

插入第i个结点

删除第i个结点

移除列表元素

没有采用虚拟头结点的方法

采用虚拟头结点的方法

设计链表

反转链表

知识点：链表

链表：存储每一个元素的同时，还存储下一个元素的地址

结点包含数据域和指针域

链表有三种：单链表、双向链表和循环链表

头指针：指向链表第一个结点的指针

单链表由表头唯一确定，所以可以用头指针来代表整个链表

首元结点：链表中存储第一个数据元素a1的结点

空表：头结点的指针域为空

设置头结点的好处：1.方便处理首元结点；2.便于空表和非空表的统一处理

顺序表：随机存取；链表：顺序存取

 

头结点 -> 第1个结点 -> 第2个结点 -> ··· -> 第n个节点

  1. 构建结点 struct

  2. 生成头结点

  3. 生成子结点

  4. 向节点中存数据

  5. 构建结点之间的关系

结点定义

构建结点

用结构体struct来定义结点

指向头结点的指针，代表整个链表，使用LinkList L;定义 而指向某个结点的指针，使用Lnode* p;定义

 typedef struct Lnode
 {
     ElemType data; // ElemType指数据类型
     struct Lnode *next; // 自己定义自己，嵌套定义
 } Lnode, *LinkList; // Lnode：指Lnode结点；LinkList：指向结构体Lnode的指针
 // Lnode a; a.data来访问
 // Lnode* L;和LinkList L;效果相同，都是定义一个指向链表的指针

为统一链表的操作，通常定义：

 typedef struct
 {
     char num[8];
     char name[8];
     int score;
 } ElemType;
 ​
 typedef struct Lnode 
 {
     ElemType data;
     struct Lnode* next;
 } Lnode, *LinkList;

单链表的初始化

即构造一个空表

 Status initList(LinkList &L)
 {
     L = new Lnode; // 生成一个大小为Lnode的内存，将地址赋值给L
     L->next = NULL; 
     return OK;
 }

->操作指针指向对象的某一个成员

判断一个链表是否为空

头结点指针与是否为空

 int ListEmpty(LinkList L)
 {
     if (L->next) // 非空
         return 0;
     else
         return 1;
 }

单链表的销毁

从头结点开始，依次释放所有结点

Status DestroyList(LinkList &L)
 {
     Lnode *p;
     while L // 非空
     {
       p = L;
       L = L->next;
       delete p;
     }
     return OK;
 }

清空单链表

依次释放所有结点，并将头结点指针域设置为空

 int RemoveList(LinktList &L)
 {
     Londe *p = L->next;
     Londe *q = p;
     while p
     {
         q = p->next;
         delete p;   
         p = q;
     }
     L->data = NULL;
     return OK;
 }

求链表表长

从首元结点开始，依次计数所有结点

 Status ListLength(LinkList &L)
 {
     if (L)
         return 0;
     Londe *p = L->next;
     int count = 1;
     while p
     {
         p = p->next;
         count++;
     }
     return OK;
 }

取单链表中第i个元素

从链表的头指针出发，顺着next逐个结点向下搜索，直到搜索到第i个元素

  1. 声明一个指针p指向链表第一个结点，初始化j从1开始；

  2. 当j<i时，就遍历链表，让指针p向后移动，不断指向下一个结点，j累加1；

  3. 当j==i时，找到第i个结点

 Status GetElem(LinkList L, int i, ElemType &e)
 {
     p = L->next;
     int j = 1;
     while (p && j < i)
     {
         p = p->next;
         j++;
     }
     if (!p || j > i) // 第i个元素不存在
         return ERROR;
     e = p->data;
     return OK;
 }

按值查找

根据指定数据获取该数据所在的位置

 int LocateElem(LinkList L, ElemType e)
 {
     Lnode *p = L->next; // 此时p指向第一个结点
     count = 1;
     while (p->data != e)
     {
         p = p->next;
         count++;
     }
     if (p->data == e)
         return count;
     else
         return 0;
 }

插入第i个结点

在第i个结点前插入值为e的新结点

关键：找到第i-1个结点

 Status InsertElem(LinkList &L, int i, ElemType e)
 {
     Lnode *p = L->next; // 此时p指向第一个结点
     int j = 1;
     while (j < i -1 && p) // 指针不为空
     {
         p = p->next;
         j++;
     }
     // 循环完后，p指向第i-1个结点
     if (!p || j > i - 1)
         return ERROR;
     Lnode *s = new Lnode; // 生成一个空结点
     s->data = e;
     s->next = p->next;
     p->next = s;
     return OK;
 }

删除第i个结点

 Status RemoveElem(LinkList &L, int i, ElemType &e)
 {
     Londe *p = L->next;
     int j = 1;
     while (j < i - 1 && p)
     {
         p = p->next;
         j++;
     }
     // 循环完后，p指向第i-1个结点
     if (!p || j > i - 1)
         return ERROR;
     Lnode *s = p->next; // s指向第i个结点
     p->next = s->next; 
     e = s->data;
     delete s;
     return OK;
 }

温馨提示：在力扣中，关于链表的题目，都是没有头结点的（也有的人叫做虚拟头结点）

操作指针时，一定要先判断指针是否为空，若为空，则编译报错（操作空指针）

移除列表元素

题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例：

 输入：head = [1,2,6,3,4,5,6], val = 6
 输出：[1,2,3,4,5]
 输入：head = [], val = 1
 输出：[]

思路：这道题目还是比较简单的，主要要考虑要删除节点的位置，即要删除的节点是否是首元结点，所谓首元结点，是指储存元素的第一个节点，head指向该节点。为了统一删除操作，可以采用(虚拟)头节点的方式。

删除节点的流程：

假设cur指向我们要删除的节点，pre指向要删除节点的前一个节点，即pre->next等于cur

 pre->next = cur->next; // 如果单次删除的话，这一句就可以了
 cur = cur->next; // 为下一次删除做准备

没有采用虚拟头结点的方法

 ListNode* removeElements(ListNode* head, int val) {
     if (head == NULL) // 如果是空链表，直接返回
         return head;
     while (head->val == val) // 链表第一个元素是或前几个元素都是val
     {
         head = head->next;
         if (head == NULL)
             return head;
     }
     // 快慢指针
     ListNode *pre = head;
     ListNode *cur = head->next;
     while (cur != NULL)
     {
         if (cur->val == val)
         {
             pre->next = cur->next; // 删除结点-步骤1
             cur = cur->next; // 删除结点-步骤2
         }
         else
         {
             pre = cur;
             cur = cur->next;
         }
     }
     return head;
 }

采用虚拟头结点的方法

 ListNode* removeElements(ListNode* head, int val) {
     if (head == NULL) // 如果是空链表，直接返回
         return head;
     ListNode *dummyNode = new ListNode(-1, head); // 虚拟头结点 dummyNode->val为-1，dummyNode->next为head（相当于调用了结构体ListNode的构造函数）
     ListNode *pre = dummyNode;
     ListNode *cur = dummyNode->next; // 或者ListNode *cur = head;
     while (cur != NULL)
     {
         if (cur->val == val)
         {
             pre->next = cur->next; // 删除结点的两步操作 记住！
             cur = cur->next;
         }
         else
         {
             pre = cur;
             cur = cur->next;
         }
     }
     // return head; // 注意：直接return head; 是错误的 我们想要的head应该是dummyNode的下一个结点，而非本来的head（这两个head有可能一样，有可能不同）
     head = dummyNode->next;
     return head;
 }

设计链表

题目描述：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

 MyLinkedList linkedList;      // 实例化类对象
 linkedList.addAtHead(1);
 linkedList.addAtTail(3);
 linkedList.addAtIndex(1,2);   // 链表变为1-> 2-> 3
 linkedList.get(1);            // 返回2
 linkedList.deleteAtIndex(1);  // 现在链表是1-> 3
 linkedList.get(1);            // 返回3

踩过的坑：

  1. index从0开始；

  2. 写类方法时，考虑是否要判断index的范围；

  3. 最好采用虚拟头结点的方法；

  4. 在写addAtIndex方法时，index可以等于链表长度，相当于在链表尾插入；

具体代码：

 class MyLinkedList {
 public:
     struct Node
     {
         int val;
         Node *next;
         Node(int val):val(val), next(nullptr){}
     };
 ​
 private:
     // 私密属性前加 '_'
     Node *_dummyNode; // 虚拟头结点
     int _size; // 记录链表长度
 ​
 public:
     MyLinkedList()
     {
         _dummyNode = new Node(-1); // 调用构造函数
         _size = 0;
     }
 ​
     int get(int index) // index从0开始
     {
         if (index < 0 || index > _size - 1)
         {
             return -1;
         }
         Node *p = _dummyNode->next;
         for (int i = 0; i < index; i++)
         {
             p = p->next;
         }
         return p->val;
     }
 ​
     void addAtHead(int val)
     {
         Node *node = new Node(val);
         node->next = _dummyNode->next;
         _dummyNode->next = node;
         _size++;
     }
 ​
     void addAtTail(int val)
     {
         Node *node = new Node(val);
         if (_dummyNode->next == nullptr)
         {
             _dummyNode->next = node;
         }
         else
         {
             Node *p = _dummyNode->next;
             while (p->next != nullptr)
             {
                 p = p->next;
             }
             p->next = node;
         }
         _size++;
     }
 ​
     void addAtIndex(int index, int val)
     {
         if (index < 0 || index > _size) // 为什么这里不是大于_size - 1 原因：当index=_size时，相当于往链表尾添加元素
         {
             return;
         }
         Node *node = new Node(val);
         Node *p = _dummyNode;
         for (int i = 0; i < index; i++)
         {
             p = p->next;
         }
         node->next = p->next;
         p->next = node;
         _size++;
     }
 ​
     void deleteAtIndex(int index)
     {
         if (index < 0 || index > _size - 1)
             return;
         Node *p = _dummyNode;
         for (int i = 0; i < index; i++)
         {
             p = p->next;
         }
         Node *de = p->next;
         p->next = de->next;
         delete de;
         _size--;
     }
 };

反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：

 输入：head = [1,2,3,4,5]
 输出：[5,4,3,2,1]
 输入：head = [1,2]
 输出：[2,1]
 输入：head = []
 输出：[]

思路：采用双指针的方法，我代码里的lat指针其实就相当于卡哥视频里的临时指针。简单来说，pre指向cur的前一节点，lat最开始和cur指向同一个节点，在每次循环时，用lat来保存cur的下一节点。

具体代码：

 ListNode* reverseList(ListNode* head) {
     if (head == nullptr || head->next == nullptr)
         return head;
     ListNode *pre = head;
     ListNode *cur = pre->next;
     ListNode *lat = cur;
     pre->next = nullptr; // 不能与上上一句调换顺序
     while (cur->next != nullptr)
     {
         lat = cur->next;
         cur->next = pre;
         pre = cur;
         cur = lat;
     }
     cur->next = pre;
     head = cur;
     return head;
 }

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

笔记

链表

算法

数据结构

代码随想录算法训练营第三天 ｜ 203.移除链表元素、707.设计链表、206.反转链表 的相关文章

随机推荐

  • 【转载】探索推荐引擎内部的秘密

    原网址 https www ibm com developerworks cn web 1103 zhaoct recommstudy1 index html icomments 这是2011年ibm发布的文章 较为通俗易懂 适合想入门推荐

  • 配置msf连接postgresql数据库

    BackTrack 5 R3版本的Metasploit在每次的升级后总会出现奇奇怪怪的错误 主要是Ruby的库出错 网上找了一些解决的办法 但每次更新后又会出错 蛋碎 解决方法 BackTrack 5中默认自动开启端口7337 1 查看Po

  • Zabbix监控MariaDB服务

    文章目录 1 概述监控MariaDB服务主机 2 安装MariaDB服务和配置MariaDB 3 配置Zabbix的userparameter mysql conf 文件模板 4 在Web配置模板 5 在server进行压力测试mysql服

  • svg实现文本的垂直居中对齐样式

    项目中用到表格内画折线趋势图 本人使用的svg绘制简单折线 没有数据的单元格显示文字 为了不影响表格的宽度自适应 就想到在svg上写文字 于是就有了在svg上对文字样式进行垂直居中的需求 上代码

  • Linux教程：在虚拟机中如何配置Linux系统网络环境 ？

    对于很多初学Linux 的同学 大多选择使用虚拟机来展开学习 可以方便的做实验 修改 测试 不必害怕出问题 可以随便折腾 大不了换一个虚拟机 原来的系统不受任何影响 但由于不是实体pc机 使用难免受限 如果配置不好 后期开发必受其累 比如

  • C++Primer（4-8章）

    第四章 表达式 求值顺序 C 中没有明确规定大多数运算符的求值顺序 因此我们要避免 改变了某个运算对象的值 又在表达式其他地方使用这个运算对象 这种情况出现 赋值运算满足右结合律 在输出表达式中使用条件运算符 条件运算符的优先级非常低 因此

  • java修改AD域用户密码使用SSL连接方式

    正常情况下 JAVA修改AD域用户属性 只能修改一些普通属性 如果要修改AD域用户密码和userAccountControl属性就得使用SSL连接的方式修改 SSL连接的方式需要操作以下步骤 1 安装AD域证书服务 2 证书颁发机构中设置以

  • 【C语言】结构体中的函数指针

    目录 一 函数指针是什么 二 结构体中的函数指针 一 函数指针是什么 函数指针是指向函数的指针变量 通常我们说的指针变量是指向一个整型 字符型或数组等变量 而函数指针是指向函数 函数指针可以像一般函数一样 用于调用函数 传递参数 正确形式

  • 2.【Python】分类算法—Logistic Regression

    2 Python 分类算法 Logistic Regression 文章目录 2 Python 分类算法 Logistic Regression 前言 一 Logistic Regression模型 1 线性可分和线性不可分 2 Logis

  • 二.全局定位--开源定位框架livox-relocalization实录数据集测试

    相关博客 二十五 SLAM中Mapping和Localization区别和思考 goldqiu的博客 CSDN博客 二十五 SLAM中Mapping和Localization区别和思考 goldqiu的博客 CSDN博客 基于固态雷达的全局

  • 【Flink系列】- RocksDB增量模式checkpoint大小持续增长的问题及解决

    背景 Flink版本 1 13 5 一个使用FlinkSQL开发的生产线上任务 使用Tumble Window做聚和统计 并且配置table exec state ttl为7200000 设置checkpoint周期为5分钟 使用rocks

  • cr2格式缩略图不显示_苹果HEIC格式照片如何快速在windows电脑上查看

    相信很多人一定遇到这样的一个情况 出去旅游玩了一阵 辛辛苦苦回来将iphone拍的照片拷贝到windows电脑 windows7系统 上 想寻找一些心仪的照片 却发现是如下的样子 OMG 欺负我买不起苹果电脑是吧 我拍的是啥 什么也看不到

  • Linux —— XShell6远程操控开机、重启和用户登录注销

    1 关机 重启命令 shutdown h now 表示立即关机 shutdown h 1 表示一分钟后关机 shutdown r now 表示立即重启 halt 直接使用 等价于关机 reboot 就是重启系统 sync 把内存的数据同步到

  • 会议OA项目----我的审批

    前言 上一篇博客我将我的会议的送审和会议排座这两个功能完成 送审之后就到了审批阶段 那么这次做的就是 我的审批 一 实现思路 根据产品原型图 见产品原型图 我的审批界面与我的会议界面大同小异 那么我们可以调用之前的写好的SQL语句 只不过将

  • 文件上传/下载接口（超简单的教程来了）

    前言 文件上传 下载接口与普通接口类似 但是有细微的区别 如果需要发送文件到服务器 例如 上传文档 图片 视频等 就需要发送二进制数据 上传文件一般使用的都是 Content Type multipart form data 数据类型 可以

  • java懒加载注解_一分钟学习Spring注解之懒加载@Lazy

    先声明 本篇文章非常简单属于一分钟学会使用系列 不深入讲解原理 如果要学习源码 可以看小编Spring源码解析系列 什么是懒加载 懒加载就是不使用不加载 使用的时候才去加载 Spring默认不是懒加载 而是启动加载 就在Spring上下文启

  • rac集群节点级联重启故障分析

    author skate time 2012 07 16 无意中发现以前处理故障写的一篇文章 记录下来以备查找 rac集群节点级联重启故障分析 环境 os linux db rac10g ocfs2 rac数据库环境实际包含两个集群 一个是

  • linux socket非阻塞之connect 函数

    1 connect原型 include

  • 联想E480安装MacOS苹果系统记录

    联想E480安装MacOS记录 联想E480安装黑苹果 自己有用IPad和Iphone 但Mac OS却没怎接触过 于是萌生了转用Mac OS的想法 用自用的联想E480装个黑果 为了方便软件上的互补 双系统优先 网上搜搜转转没发现有E48

  • 代码随想录算法训练营第三天 ｜ 203.移除链表元素、707.设计链表、206.反转链表

    目录 知识点 链表 结点定义 单链表的初始化 判断一个链表是否为空 单链表的销毁 清空单链表 求链表表长 取单链表中第i个元素 按值查找 插入第i个结点 删除第i个结点 移除列表元素 没有采用虚拟头结点的方法 采用虚拟头结点的方法 设计链表

热门标签