网站的关于页面,重庆品牌型网站建设多少钱,茂名专业网站建设,常用来做网站首业的是代码随想录算法训练营第三天 | 203.移除链表元素、707.设计链表、206.反转链表 文章目录 代码随想录算法训练营第三天 | 203.移除链表元素、707.设计链表、206.反转链表1 链表理论基础1.1 链表的定义1.2 链表的类型1.3 链表的存储方式1.4 链表的操作性能分析1.5 链表和数组的区…代码随想录算法训练营第三天 | 203.移除链表元素、707.设计链表、206.反转链表 文章目录 代码随想录算法训练营第三天 | 203.移除链表元素、707.设计链表、206.反转链表1 链表理论基础1.1 链表的定义1.2 链表的类型1.3 链表的存储方式1.4 链表的操作性能分析1.5 链表和数组的区别 2 LeetCode 203.移除链表元素2.1 不带虚拟头节点的删除操作2.2 带虚拟头节点的删除操作 3 LeetCode 707.设计链表3.1 Python版本代码3.2 C版本代码 4 LeetCode 206.反转链表4.1 双指针法4.2 递归法4.3 头插法 1 链表理论基础
链表是一种常见的数据结构它在计算机科学中用于存储一系列元素链表的特点是其元素不必在内存中连续存储这种结构提供了在序列内部插入和删除元素的高效操作下面将结合408相关知识介绍一下有关链表的一些基础知识以及链表与数组的区别。
1.1 链表的定义
链表由一系列称为“节点”的元素组成每个节点包含两个部分数据和指向列表中下一个节点的引用或链接在最简单的形式中每个节点包含数据和一个指向列表中下一个节点的指针即数据域data和指针域next。
1.2 链表的类型 单向链表每个节点只有指向下一个节点的链接其节点类型定义如下参考王道数据结构单链表定义 typedef struct LNode{ElemType data; //数据域struct LNode *next; //指针域
}LNode, *LinkList利用单链表可以解决顺序表需要大量连续存储单元的缺点但单链表附加指针域也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中所以单链表是非随机存取的存储结构即不能直接找到表中某个特定的结点。查找某个特定的结点时需要从表头开始遍历依次查找。 通常用头指针来标识一个单链表如单链表L头指针为NULL时表示一个空表。此外为了操作上的方便在单链表第一个结点之前附加一个结点称为头结点。头结点的数据域可以不设任何信息也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点如下图所示来源于王道数据结构 头结点和头指针的区分:不管带不带头结点头指针都始终指向链表的第一个结点而头结点是带头结点的链表中的第一个结点结点内通常不存储信息。 引入头结点后可以带来两个优点 ①由于第一个数据结点的位置被存放在头结点的指针域中因此在链表的第一个位置上的操作和在表的其他位置上的操作一致无须进行特殊处理。 ②无论链表是否为空其头指针都是指向头结点的非空指针(空表中头结点的指针域为空)因此空表和非空表的处理也就得到了统一。 双向链表每个节点有两个链接一个指向前一个节点即prior指针另一个指向下一个节点即next指针是为了克服单链表的缺点所以引入了双链表。 其节点类型定义如下参考王道数据结构双链表定义 typedef struct DNode{ElemType data; //数据域struct DNode *prior,*next; //前驱和后继指针
}LNode, *DLinklist其表示示意图如下图所示来源于王道数据结构 双链表在单链表的结点中增加了一个指向其前驱的prior 指针因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上与单链表有着较大的不同。这是因为“链”变化时也需要对prior 指针做出修改其关键是保证在修改的过程中不断链。此外双链表可以很方便地找到其前驱结点因此插入、删除操作的时间复杂度仅为O(1)。 循环链表链表中的最后一个节点指向第一个节点或其他之前的节点形成一个环循环单链表和单链表的区别在于表中最后一个结点的指针不是NULL而改为指向头结点从而整个链表形成一个环如下图所示来源于王道数据结构 在循环单链表中表尾结点*r的next域指向L故表中没有指针域为NULL的结点因此循环单链表的判空条件不是头结点的指针是否为空而是它是否等于头指针。 循环单链表的插入、删除算法与单链表的几乎一样所不同的是若操作是在表尾进行则执行的操作不同以让单链表继续保持循环的性质。当然正是因为循环单链表是一个“环”因此在任何一个位置上的插入和删除操作都是等价的无须判断是否是表尾。 在单链表中只能从表头结点开始往后顺序遍历整个链表而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环单链表不设头指针而仅设尾指针以使得操作效率更高。其原因是若设的是头指针对在表尾插入元素需要O(n)的时间复杂度而若设的是尾指针rr-next即为头指针对在表头或表尾插入元素都只需要O(1)的时间复杂度。 循环双链表结合了双向链表和循环链表的特点不同的是在循环双链表中头节点的prior指针还要指向表尾节点其表示示意图如下图所示来源于王道数据结构 在循环双链表L中某结点*p为尾结点时p-nextL当循环双链表为空表时其头结点的prior域和next域都等于L。
1.3 链表的存储方式
链表中的节点不需要在内存中连续存储这一点和数组相反每个节点只需存储其数据部分和指向列表中下一个和/或前一个节点的指针这种存储方式使得链表在插入和删除操作时能够较少地移动或重新排列其他元素如下图所示来源于代码随想录
1.4 链表的操作性能分析
插入和删除链表可以在任何位置高效地插入或删除节点这些操作的时间复杂度通常是 O(1)但如果需要找到特定位置则可能需要 O(n) 的时间其中 n 是链表的长度。搜索搜索一个元素在链表中的位置或者搜索链表中的特定元素的效率较低时间复杂度为 O(n)。访问对于链表的随机访问例如访问第 n 个元素效率低下因为需要从头节点开始遍历链表时间复杂度为 O(n)。
1.5 链表和数组的区别
特性数组链表存储方式在内存中连续存储元素元素分布在内存中不连续的节点中访问时间快速随机访问O(1)需要从头遍历O(n)插入和删除操作可能需要移动元素O(n)在已知位置快速操作O(1)寻找位置时O(n)内存利用率可能造成内存浪费或空间不足动态分配高效利用内存内存分配静态或动态内存分配总是使用动态内存分配实现实现简单支持多种操作实现复杂需要额外内存存储指针应用场景元素数量固定频繁访问元素数量变化大频繁插入删除
2 LeetCode 203.移除链表元素
题目链接https://leetcode.cn/problems/remove-linked-list-elements/description/ 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1,2,6,3,4,5,6], val 6
输出[1,2,3,4,5]示例 2 输入head [], val 1
输出[]示例 3 输入head [7,7,7,7], val 7
输出[]提示 列表中的节点数目在范围 [0, 104] 内1 Node.val 500 val 50 在移除链表元素时我们需要考虑是否需要给原始链表添加虚拟头节点也叫哨兵节点因为如果直接在原始链表上我们需要首先判断是否删除的是head所指的头节点头节点的删除和其他的节点的删除是不一样的但是如果我们使用虚拟头节点来进行操作的话可以统一删除节点的操作下面我们将两种情况的代码都写出来。
2.1 不带虚拟头节点的删除操作
1Python版本代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head, val):# 首先移除头部需要删除的节点while(head ! None and head.val val): # 注意head ! Nonehead head.next# 现在头部节点不需要删除cur指向第一个不需要删除的节点cur headwhile(cur ! None and cur.next ! None): # 注意cur.next ! Noneif cur.next.val val: # 如果下一个节点需要删除cur.next cur.next.next # 删除下一个节点else: # 如果下一个节点不需要删除cur cur.next # cur指向下一个节点return head2C版本代码
/*** 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) {// 首先移除头部需要删除的节点while (head ! nullptr head-val val) {head head-next;}// 现在头部节点不需要删除ListNode* cur head;// 遍历链表while (cur ! nullptr cur-next ! nullptr) {if (cur-next-val val) {// 如果下一个节点需要删除cur-next cur-next-next;} else {// 如果下一个节点不需要删除cur cur-next;}}return head;}
};2.2 带虚拟头节点的删除操作
1Python版本代码
class Solution:def removeElements(self, head, val):dummy ListNode(0, head) # 创建虚拟头节点dummy.next head # 虚拟头节点指向headcur dummy # cur指向虚拟头节点while cur.next:if cur.next.val val:cur.next cur.next.nextelse:cur cur.nextreturn dummy.next2C版本代码
class Solution {
public:ListNode* removeElements(ListNode* head, int val) {// 创建一个虚拟头节点ListNode dummy(0);dummy.next head;// cur 指向虚拟头节点ListNode* cur dummy;// 遍历链表while (cur-next ! nullptr) {if (cur-next-val val) {// 删除下一个节点cur-next cur-next-next;} else {// 移动到下一个节点cur cur-next;}}return dummy.next;}
};本题比较简单主要是介绍两种处理方法最关键是要理解虚拟头结点的使用技巧这个对链表题目很重要我更偏向于使用虚拟头节点来进行操作因为这样可以统一删除操作同样添加操作也类似可以简化代码。
3 LeetCode 707.设计链表
题目链接https://leetcode.cn/problems/design-linked-list/description/ 你可以选择使用单链表或者双链表设计并实现自己的链表。 单链表中的节点应该具备两个属性val 和 next 。val 是当前节点的值next 是指向下一个节点的指针/引用。 如果是双向链表则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。 实现 MyLinkedList 类 MyLinkedList() 初始化 MyLinkedList 对象。int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1 。void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后新节点会成为链表的第一个节点。void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度那么该节点会被追加到链表的末尾。如果 index 比长度更大该节点将 不会插入 到链表中。void deleteAtIndex(int index) 如果下标有效则删除链表中下标为 index 的节点。 示例 输入
[MyLinkedList, addAtHead, addAtTail, addAtIndex, get, deleteAtIndex, get]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]解释
MyLinkedList myLinkedList new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1-2-3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在链表变为 1-3
myLinkedList.get(1); // 返回 3提示 0 index, val 1000请不要使用内置的 LinkedList 库。调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。 我们后续有关链表的操作都将默认使用虚拟头节点这样会使代码看起来更加简洁上面也介绍过了。
这道题目就是考察我们对链表常见的操作的掌握情况也就是下面的这几种操作
获取链表第index个节点的数值在链表的最前面插入一个节点在链表的最后面插入一个节点在链表第index个节点前面插入一个节点删除链表的第index个节点
这道题目掌握牢固了基本上链表操作也就可以了其他类型的链表也都是类似的操作。
需要注意的是在链表的插入操作中我们需要注意插入操作的执行顺序防止出现断链的情况这一点在408数据结构中也经常考察就比如在刚过去的2024年408考试中第一道选择题就考察了链表的操作需要特别注意。
下面我们直接写出每个函数的代码。
3.1 Python版本代码
class ListNode:def __init__(self, val 0, next None):self.val valself.next nextclass MyLinkedList:def __init__(self):self.dummy ListNode()self.size 0# 获取链表中下标为 index 的节点的值。如果下标无效则返回 -1 。def get(self, index: int) - int:if index 0 or index self.size: return -1cur self.dummy.nextwhile index:cur cur.nextindex - 1return cur.val# 在链表头部插入一个节点该节点的值为 val 。插入后新节点将成为链表的第一个节点。def addAtHead(self, val: int) - None:self.dummy.next ListNode(val, self.dummy.next)self.size 1# 将值为 val 的节点插入到链表中的第一个值为 val 的节点之后。def addAtTail(self, val: int) - None:cur self.dummywhile cur.next:cur cur.nextcur.next ListNode(val)self.size 1# 在链表中的第 index 个节点之前插入值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。def addAtIndex(self, index: int, val: int) - None:if index 0 or index self.size:returncur self.dummywhile index:cur cur.nextindex - 1cur.next ListNode(val, cur.next)self.size 1# 删除链表中的第 index 个节点。如果 index 等于链表的长度则删除链表中的最后一个节点。def deleteAtIndex(self, index: int) - None:if index 0 or index self.size:returncur self.dummywhile index:cur cur.nextindex - 1cur.next cur.next.nextself.size - 13.2 C版本代码
// class ListNode {
// public:
// int val;
// ListNode *next;
// ListNode(int val 0, ListNode *next nullptr) : val(val), next(next) {}
// };class MyLinkedList {
public:// 构造函数MyLinkedList() {dummy new ListNode(0); // 创建一个虚拟头节点size 0;}// 析构函数释放链表占用的内存~MyLinkedList() {ListNode* cur dummy;while (cur ! nullptr) {ListNode* next cur-next;delete cur; // 使用 delete 释放内存cur next;}}// 获取指定索引的节点值int get(int index) {if (index 0 || index size) {return -1;}ListNode* cur dummy-next;while (index--) {cur cur-next;}return cur-val;}// 在链表头部添加节点void addAtHead(int val) {dummy-next new ListNode(val, dummy-next);size;}// 在链表尾部添加节点void addAtTail(int val) {ListNode* cur dummy;while (cur-next ! nullptr) {cur cur-next;}cur-next new ListNode(val);size;}// 在指定索引添加节点void addAtIndex(int index, int val) {if (index 0 || index size) {return;}ListNode* cur dummy;while (index--) {cur cur-next;}cur-next new ListNode(val, cur-next);size;}// 删除指定索引的节点void deleteAtIndex(int index) {if (index 0 || index size) {return;}ListNode* cur dummy;while (index--) {cur cur-next;}ListNode* temp cur-next;cur-next cur-next-next;delete temp; // 删除节点size--;}private:ListNode* dummy; // 虚拟头节点int size; // 链表大小
};对于释放内存操作需要注意的是在 C 中应当使用 delete 而非 free() 来释放由 new 分配的内存new 和 delete 是 C 中处理动态内存的标准方式它们不仅分配和释放内存还调用对象的构造函数和析构函数相比之下malloc() 和 free() 是 C 语言中的函数它们只处理内存的分配和释放而不调用构造函数和析构函数。
4 LeetCode 206.反转链表
题目链接https://leetcode.cn/problems/reverse-linked-list/ 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3 输入head []
输出[]提示 链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 **进阶**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题 这道题目有点像有一年的408算法题我去翻了一下是2019年的算法题那道题目需要反转三次但是这两道题目都是类似的操作下面我贴出408的2019年算法题
下面是2024版王道数据结构中的解法 回到这题来这道题目我们可以首先考虑使用双指针方法来有效的反转链表。
4.1 双指针法
我们使用两个指针cur 和 pre。cur 指向当前要处理的节点而 pre 存储 cur 的前一个节点通过遍历链表逐个改变节点的指向直到链表完全反转需要注意的是反转代码的执行顺序我们需要设置一个临时指针temp保存当前节点避免首先反转之后cur的值已经变化然后出现指向错误。在每次迭代中将 cur 的 next 指针指向 pre当 cur 为 None 时pre 将指向新的头节点完成反转。
1Python版本实现代码
class Solution:def reverseList(self, head):cur head # 当前节点pre None # 前一个节点while cur: # 当前节点不为空temp cur.next # 临时节点cur.next pre # 当前节点指向前一个节点pre cur # 前一个节点指向当前节点cur temp # 当前节点指向下一个节点return pre # 返回前一个节点2C版本实现代码
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur head; // 当前节点ListNode* pre nullptr; // 前一个节点while (cur ! nullptr) {ListNode* temp cur-next; // 临时节点保存当前节点的下一个节点cur-next pre; // 当前节点指向前一个节点pre cur; // 前一个节点指向当前节点cur temp; // 当前节点指向下一个节点}return pre; // 返回前一个节点即新的头节点}
};4.2 递归法
我们还可以使用递归的方法简化双指针法的代码但是不推荐新手首先写递归方法因为递归方法比较抽象难以理解更重要的还是双指针的实现思路我们先写出双指针的解法之后我们就可以按照双指针的思路对应的写出递归版的代码。
1Python版本实现代码
class Solution:def reverse(self, cur, pre): if cur None:return pretemp cur.nextcur.next prereturn self.reverse(temp, cur)def reverseList(self, head):return self.reverse(head, None)2C版本实现代码
class Solution {
public:ListNode* reverse(ListNode* cur, ListNode* pre) {if (cur nullptr) {return pre;}ListNode* temp cur-next;cur-next pre;return reverse(temp, cur);}ListNode* reverseList(ListNode* head) {return reverse(head, nullptr);}
};4.3 头插法
另外我们再介绍一种实现思路那就是利用链表的头插法来解决这道题目头插法的基本思想是逐个将原链表的节点插入到一个新链表的头部在本题中也就是逆用头插法首先创建一个新的虚拟头节点遍历原链表每次迭代中将当前节点从原链表中移除将该节点插入到新链表的头部继续遍历直到原链表为空最后新链表的头节点即为反转后的链表头节点。
1Python版本实现代码
class Solution:def reverseList(self, head):new_head None # 新链表的头节点初始为 Nonecur headwhile cur:temp cur.next # 保存当前节点的下一个节点cur.next new_head # 将当前节点插入到新链表的头部new_head cur # 更新新链表的头节点cur temp # 移动到原链表的下一个节点return new_head2C版本实现代码
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* new_head nullptr; // 新链表的头节点初始为 nullptrListNode* cur head;while (cur ! nullptr) {ListNode* temp cur-next; // 保存当前节点的下一个节点cur-next new_head; // 将当前节点插入到新链表的头部new_head cur; // 更新新链表的头节点cur temp; // 移动到原链表的下一个节点}return new_head; // 返回新链表的头节点即反转后的头节点}
};在头插法代码中new_head 代表新链表的头节点最初为 None在每次迭代中我们将 cur当前处理的节点从原链表中移除并将其插入到新链表的头部这个过程一直持续到原链表被完全遍历最终new_head 将成为反转后链表的头节点。
头插法算是提供了另一种有效的链表反转方法特别适用于需要创建反转链表的副本的情况。
