代码随想录day3 203.移除列表元素 707.设计链表 206.反转链表

2023-12-03 00:52

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

数组是在内存中是连续分布的,但是链表在内存中可不是连续分布的。

双链表

单链表中的指针域只能指向节点的下一个节点。

双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

问题:约瑟夫环是什么?循环列表为什么能解决约瑟夫环的问题?

链表的代码:

// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

删除链表节点,对于c++需要释放内存,其他语言例如Java、Python,就有自己的内存回收机制,就不用自己手动释放了。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* virt=new ListNode(0,head);  //要加newvirt->val=0;virt->next=head;ListNode* tmp;tmp=virt;while(tmp->next!=NULL){if(tmp->next->val==val){ListNode* tmp1= tmp->next;// tmp->next =tmp1->next;// tmp1->next=NULL;tmp->next=tmp->next->next;delete tmp1;}else{tmp=tmp->next;}}head=virt->next;delete virt;return head; //必须从头节点返回才行,直接选取head节点开始返回不行}
};

参考了题解才改对的,就是主要是本来没有 head=virt->next;        delete virt; 就直接返回head,可能因为有前他指针指向head,不能直接返回。要->next得到虚拟节点的下一个。

另外,是用ListNode* virt=new ListNode(0,head); ,也就是用new什么来声明一个指针。

delete tmp1;就是指针节点。

707.设计链表  

链表操作的两种方式:

  1. 直接使用原来的链表来进行操作。
  2. 设置一个虚拟头结点在进行操作。

这道题需要自己定义链表节点结构体

MyLinkedList()是初始化函数

class MyLinkedList {
public:struct linkedNode{int val;linkedNode* next;linkedNode(int val):val(val),next(nullptr){}};MyLinkedList() {// int num=0;// linkedNode * head=new linkedNode(0);_num=0;_head=new linkedNode(0);}int get(int index) {if(_num<=index) return -1;linkedNode * tmp=_head;int tmpN=-1;while(tmp->next!=NULL){tmp=tmp->next;tmpN++;if(tmpN==index){return tmp->val;}}return -1;}void addAtHead(int val) {// linkedNode * tmp=head;linkedNode * newT=new linkedNode(val);newT->next=_head->next;_head->next=newT;_num++;}void addAtTail(int val) {linkedNode * newT=new linkedNode(val);linkedNode * tmp=_head;//int tmpN=-1;while(tmp->next!=NULL){tmp=tmp->next;}_num++;tmp->next=newT;}void addAtIndex(int index, int val) {if(index>_num) return ;linkedNode * newT=new linkedNode(val);linkedNode * tmp=_head;int tmpN=-1;while(tmp->next!=NULL){tmpN++;if(tmpN==index){newT->next=tmp->next;_num++;tmp->next=newT;return;// return tmp->val;}tmp=tmp->next;}if((tmpN+1)==index){tmp->next=newT;_num++;}return ;// tmp->next=newT;}void deleteAtIndex(int index) {linkedNode * tmp=_head;int tmpN=-1;while(tmp->next!=NULL){tmpN++;if(tmpN==index){linkedNode * tmpN=tmp->next;tmp->next=tmp->next->next;delete tmpN;_num--;return;// return tmp->val;}tmp=tmp->next;}}private:int _num;linkedNode * _head;
};/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList* obj = new MyLinkedList();* int param_1 = obj->get(index);* obj->addAtHead(val);* obj->addAtTail(val);* obj->addAtIndex(index,val);* obj->deleteAtIndex(index);*/

这道题需要自己再定义一个linkedNode结构体,一开始我不知道linkednode是不是应该放在mylinkedlist下面,mylinkedlist是初始化函数,所以是放在public下。而初始化函数是赋值初值的,在private:下面可以声明函数的私有成员变量,而不是在初始化函数声明。看了眼题解的写法才写出来,主要是忘记了c++的语法。

要注意index小于0时特判不合法。下面代码是复制过来的,为了提示自己tmp最好赋值个nullptr。

 void deleteAtIndex(int index) {if (index >= _size || index < 0) {return;}LinkedNode* cur = _dummyHead;while(index--) {cur = cur ->next;}LinkedNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;//delete命令指示释放了tmp指针原本所指的那部分内存,//被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针//如果之后的程序不小心使用了tmp,会指向难以预想的内存空间tmp=nullptr;_size--;}

 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr) return nullptr;ListNode * tmp =head;ListNode * tmpN;tmpN= tmp->next;ListNode* node;while(tmpN!=NULL){node=tmpN;tmpN=tmpN->next;node->next=tmp;tmp=node;// tmp=tmp->next;}head->next=NULL;return tmp;}
};

一遍ac,注意特判空列表的情况。比如有三个节点,第二个节点反过来要指向第一个,那原本遍历数组需要的第二个节点指向的下一个也要用其他指针指向保留。其实套用在具体例子下就比较好写了。相当于一个三个数的滑窗,每次窗口内要处理前两个数为后一个数指向前一个数。

        其实就是双指针法,题解的方法是:

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp; // 保存cur的下一个节点ListNode* cur = head;ListNode* pre = NULL;while(cur) {temp = cur->next;  // 保存一下 cur的下一个节点,因为接下来要改变cur->nextcur->next = pre; // 翻转操作// 更新pre 和 cur指针pre = cur;cur = temp;}return pre;}
};

这篇关于代码随想录day3 203.移除列表元素 707.设计链表 206.反转链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用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. 指

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

使用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

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

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

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

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