代码随想录算法训练营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

相关文章

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa