算法D3 | 链表理论基础 | 203.移除链表元素 707.设计链表 206.反转链表

链表理论基础 

建议:了解一下链接基础,以及链表和数组的区别


203.移除链表元素  

建议: 本题最关键是要理解 虚拟头结点的使用技巧,这个对链表题目很重要。题目链接/文章讲解/视频讲解

单向链表的遍历,主要是学习如何初始化链表。本题加一个dummy head遍历即可。内存方面,python会自动处理内存释放的问题,c++需要手动释放内存。

Python版本:

C++版本:

C++语法学习:

ListNode中的表示这个函数要返回的是ListNode类型的指针;

dummyHead -> next 指的是dummyHead这个对象的next属性;和python调用属性的方法不同。

遇到了一个leetcode里linkedinList结构特有的报错,链表结构需要逻辑更为完整,C++版本没有提前单独处理head=NULL的情况,需要在while里说清楚corner case。参考解决方案

707.设计链表  

建议: 这是一道考察 链表综合操作的题目,不算容易,可以练一练 使用虚拟头结点,题目链接/文章讲解/视频讲解

Python版本:

C++版本:

这里犯了一个错,line 46 一开始写成了int size=0, 导致和外部的size有重复了。“在C++中,如果一个类的成员变量是基本数据类型(如int)并且没有在构造函数中显式初始化,那么该变量的初始值是未定义的。这意味着它可能包含任何值,这个值取决于程序所运行的系统、编译器以及内存的状态。” 和局部变量一样,是未定义的,那可能是任意值。

206.反转链表 

建议:先看我的视频讲解,视频讲解中对 反转链表需要注意的点讲的很清晰了,看完之后大家的疑惑基本都解决了。题目链接/文章讲解/视频讲解

Python版本:

暴力法,内存占用 O(N), 如果双指针法仅翻转指针,则内存O(1)

暴力法:

双指针法:

仅仅是反转指针方向。

C++版本:

双指针法直接反转指针方向,这里能体现C++语法的精确了。Python版本虽然没有申明每个变量的类型,但是写的时候心里的明白pre是ListNode类型,不然会报错。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容