代码随想录算法训练营Day03 | 链表理论基础、203.移除链表元素 、707.设计链表、206.反转链表

本文主要是介绍代码随想录算法训练营Day03 | 链表理论基础、203.移除链表元素 、707.设计链表、206.反转链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

  • 链表理论基础
  • 203.移除链表元素
    • 思路与重点
  • 707.设计链表
    • 思路与重点
  • 206.反转链表
    • 思路与重点

链表理论基础

  • C/C++的定义链表节点方式:
// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
  • 数组与链表的对比:

203.移除链表元素

  • 题目链接:203. 移除链表元素 - 力扣(LeetCode)
  • 讲解链接:代码随想录 (programmercarl.com)
  • 状态:提交一次后AC。

思路与重点

  • 使用了一个虚拟头节点,指向题目给出的头节点,然后遍历链表开始删除,最后返回虚拟头节点的next指针即可。主要使用C++时不要忘记释放掉被删除节点占用的空间
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummy_head = new ListNode(-1, head);ListNode* cur = dummy_head;while(cur->next != nullptr){if(cur->next->val == val){ListNode* temp = cur->next->next;delete cur->next;cur->next = temp;}else cur = cur->next;}head = dummy_head->next;delete dummy_head;return head;}
};
  • 链表的定义具有递归的性质,因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点,可以用递归实现。
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 基础情况:空链表if (head == nullptr) {return nullptr;}// 递归处理if (head->val == val) {ListNode* newHead = removeElements(head->next, val);delete head;return newHead;} else {head->next = removeElements(head->next, val);return head;}}
};

707.设计链表

  • 题目链接:707. 设计链表 - 力扣(LeetCode)
  • 讲解链接:代码随想录 (programmercarl.com)
  • 状态:直接看题解了。

思路与重点

  • 使用虚拟头结点可以很大降低写代码的复杂程度。
  • 注意LinkedNode* cur = _dummyHead;LinkedNode* cur = _dummyHead->next;
class MyLinkedList {
public:struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};MyLinkedList() {_dummyHead = new LinkedNode(0);_size = 0;}int get(int index) {if(index < 0 || index >= _size){return -1;}LinkedNode* cur = _dummyHead->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val) {LinkedNode* newNode = new LinkedNode(val);newNode->next = _dummyHead->next;_dummyHead->next = newNode;_size++;}void addAtTail(int val) {LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(cur->next) cur = cur->next;cur->next = newNode;_size++;        }void addAtIndex(int index, int val) {if(index > _size) return;if(index < 0) index = 0;LinkedNode* newNode = new LinkedNode(val);LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}       newNode->next = cur->next;cur->next = newNode;_size++; }void deleteAtIndex(int index) {if(index >= 0 && index < _size){LinkedNode* cur = _dummyHead;while(index--){cur = cur->next;}LinkedNode* temp = cur->next;cur->next = cur->next->next;delete temp;temp = nullptr;_size--;}  else return;}private:LinkedNode* _dummyHead;int _size;
};

206.反转链表

  • 题目链接:206. 反转链表 - 力扣(LeetCode)
  • 讲解链接:代码随想录 (programmercarl.com)
  • 状态:直接去看卡哥视频了。

思路与重点

  • 用双指针法很好解决,不需要用新的链表分配空间。卡哥的视频讲的是真清晰啊,用以下的动图很好理解。

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;ListNode* temp = nullptr;while(cur){temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};
  • 也可以用递归的方式解决,递归的解决思路其实和双指针法一样。
class Solution {
public:ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}ListNode* reverse(ListNode* pre, ListNode* cur){if(!cur) return pre;ListNode* temp = cur->next;cur->next = pre;return reverse(cur, temp);}
};

这篇关于代码随想录算法训练营Day03 | 链表理论基础、203.移除链表元素 、707.设计链表、206.反转链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1141296

相关文章

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python基础语法中defaultdict的使用小结

《Python基础语法中defaultdict的使用小结》Python的defaultdict是collections模块中提供的一种特殊的字典类型,它与普通的字典(dict)有着相似的功能,本文主要... 目录示例1示例2python的defaultdict是collections模块中提供的一种特殊的字

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到