链表的表示 由于链表的特点（查询或删除元素都要从头结点开始）,所以我们只要在链表中定义头结点即可,另外如果要频繁用到链表的长度，还可以额外定义一个变量来表示。 所以之后的习题讲解中我们使用的链表都是使用定义了哨兵结点的形式。 做了这么多前期的准备工作，终于要开始我们的正餐了：链表解题常用套路--翻转！ 如图示：即给定值为 2 的结点，如何把 2 给删了。 我们知道，如果给定一个结点要删除它的后继结点是很简单的，只要把这个结点的指针指向后继结点的后继结点即可 ? 不过需要注意的是这种解题技巧只适用于被删除的指定结点是中间结点的情况，如果指定结点是尾结点，还是要老老实实地找到尾结点的前继结点，再把尾结点删除，代码如下 /** * 删除指定的结点 * @param 本文将详细讲述如何用快慢指针解决以下两大类问题 寻找/删除第 K 个结点 有关链表环问题的相关解法 寻找/删除第 K 个结点 小试牛刀之一 LeetCode 876：给定一个带有头结点 head 的非空单链表
在操作链表的时候，要格外注意二点： 边界问题，例如插入有头插尾插中间插入，要注意额外的操作； 代码顺序，防止丢失指针 单链表 ? 指向了x结点，第二步相当于将 x赋值给 x->next，即相当于x->next = x，自己指向自己，显而易见的问题：q 的地址丢失了，从 q 往后的结点都访问不到，链表断成了两截。 还是从插入，删除，查找来看，拿删除操作来分析，无非两种情况： 删除给定指针指向的结点 删除结点中值等于xxx的结点 第二种，对于单链表和双链表都需要先进行遍历，直到找到值等于给定值的结点，然后删除； 第一种 LRU 初始化启动 true LRU 缓存初始化的时候，就用了这个 accessOrder，设置为true，从而最近被访问到的数据放到了链表末尾，链表前面的数据是长时间没有使用的，从链表末尾开始访问的话 ； 如果我们遇到算法题的时候，就是需要我们用程序去解决的问题，那问题的本身就是可重复的； 无论是算法中的回溯、分治、动态规划、递归等，全部都是在找重复性的原理所以重点都是“找规律”； 分析问题： 刚刚拿到
提供包括云服务器，云数据库在内的90+款云计算产品。打造一站式的云产品试用服务，助力开发者和企业零门槛上云。
链表的表示 由于链表的特点（查询或删除元素都要从头结点开始）,所以我们只要在链表中定义头结点即可,另外如果要频繁用到链表的长度，还可以额外定义一个变量来表示。 ）,从程序逻辑性来说不是那么合理（因为结点与结点是平级，添加逻辑理应相同） 如果定义了哨兵结点，以上两个问题都可解决，来看下使用哨兵结点的链表定义 public class LinkedList { 所以之后的习题讲解中我们使用的链表都是使用定义了哨兵结点的形式。 做了这么多前期的准备工作，终于要开始我们的正餐了：链表解题常用套路--翻转！ 如图示：给定值为 2 的结点，如何把这个结点给删了。 我们知道，如果给定一个结点要删除它的后继结点是很简单的，只要把这个结点的指针指向后继结点的后继结点即可 ? 不过需要注意的是这种解题技巧只适用于被删除的指定结点是中间结点的情况，如果指定结点是尾结点，还是要老老实实地找到尾结点的前继结点，再把尾结点删除，代码如下 /** * 删除指定的结点 * @param
传统的软件可以使用自旋锁这样的同步机制，来保护gptr指针的读写。一旦旧的值不被使用，就可以将旧指针指向的数据释放。 在现代计算系统中，向gptr写入a、b、c这样的值，并发的读者要么看到一个NULL指针要么看到指向新结构gptr的指针，不会看到中间结果。也就是说，对于指针赋值来说，某种意义上这种赋值是原子的。 事实上，在没有配置CONFIG_PREEMPT的内核里，这对原语就是空函数。在可抢占内核中，这这对原语就是关闭/打开抢占。 rcudereference()原语用一种“订阅”的办法获取指定指针的值。 不过，刚好在取出指向被删除元素指针后被延迟的读者（比如，由于中断、ECC内存错误），就有可能在删除后还看见链表元素的旧值。因此，我们此时有两个版本的链表，一个有元素“5、6、7”，另一个没有。 3; 5 list_replace_rcu(&p->list, &q->list); 6 synchronize_rcu(); 7 kfree(p); 链表的初始状态包括指针p都和“删除”例子中一样
删除链表指定位置结点时间复杂度分析： 如果是删除头结点，则虚拟头结点就是头结点的前一个结点，因此时间复杂度是O(1)； 如果是删除链表末尾添加结点，则需从头遍历链表直到尾部结点的前一个结点，因此此时的时间复杂度是 然后定义虚拟结点prev，其数据域值为NULL。定义变量cur指向链表中的头结点。 ? 接着，开始遍历链表，对于变量cur所指向的下一个结点，我们用变量nextNode表示。 ? 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 具体思路，可看如下的动画演示： 这里你可能会问为什么慢指针slow初始指向链表头结点而快指针fast初始指向链表头结点的下一个结点？ 原因在于在如下的代码实现中，while循环的判断条件是slow! 但如果是要查找上一个结点，那么最坏时间复杂度就是O(n)了，因为每次都要从头开始遍历查找链表中的每个结点。 为了解决这个问题呢，就有了双向链表。
4.3 特别值得一提的是，如果链表删除仅剩的一个元素后，rear 指针就变成野指针了。这时候，需要让 rear 指针指向头结点。也许你会对头结点存在的意义产生怀疑，似乎没有它也不影响增删的操作。 那么为何队列还特被强调要有头结点呢？这主要是为了防止删除最后一个有效数据结点后， front 指针和 rear 指针变成野指针，导致队列没有意义了。 同时，哈希表中的 key 是不允许重复的，在重复性非常高的数据中，哈希表也不是个好的选择。 三、算法思维基础 1、递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。 2、分治法的使用必须满足 4 个条件： 问题的解决难度与数据规模有关； 原问题可被分解； 子问题的解可以合并为原问题的解； 所有的子问题相互独立。 3、面对一个实际的算法问题，我们需要从以下几个步骤思考如何解决问题： 复杂度分析。估算问题中复杂度的上限和下限。 定位问题。根据问题类型，确定采用何种算法思维。 数据操作分析。
循环链表可以用来解决约瑟夫环问题。 ? 链表的存储方式 了解完链表的类型，再来说一说链表在内存中的存储方式。 数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。 这是因为平时在刷leetcode的时候，链表的节点都默认定义好了，直接用就行了，所以同学们都没有注意到链表的节点是如何定义的。 而在面试的时候，一旦要自己手写链表，就写的错漏百出。 但是这个构造函数不会初始化任何成员变化，下面我来举两个例子： 通过自己定义构造函数初始化节点： ListNode* head = new ListNode(5); 使用默认构造函数初始化节点： ListNode * head = new ListNode(); head->val = 5; 所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！ 可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。 但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
L，如何建立链表在这里就不重复说了，不了解的可以看上一篇文章，然后将头结点传入，就拆分成了两个链表。 先来看看定义： 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。 从定义中能够知道，双链表和单链表的唯一区别就是，双链表多了一个能够指向直接前驱结点的指针域，能够实现双向访问。 else{ return 0; } } 插入结点 接下来又到了比较难的环节了，在双链表中的插入、删除操作和单链表十分类似，但又有些许不同，在双链表中，插入和删除的操作涉及到两个指针域的变化，所以相对要更复杂一些 同样简单分析一下，这道题其实很简单，通过遍历双链表L，然后使用头插法建立链表即可完成，具体如何实现就看大家的了。我会在下一篇专栏文章中揭晓此题答案。
List是stl实现的双向链表，与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。 1.定义和初始化 list<int> lst1;//创建空list 定义一个空的链表lst1 list<int> lst2(3);//创建含有三个元素的list 定义一个长度为3的链表，默认初始化为 0 list<int> lst3(3,2);//创建含有三个元素的list 定义一个长度为3，元素值为2的链表 list<int> lst4(lst2);//使用lst2初始化lst4，初始化后lst2 删除相邻重复元素 删除整个链表中的重复结点，使得链表每个结点都不同 3.元素获取（遍历方法） for(list<int>::const_iterator iter = lst1.begin();iter = lst1.end();iter++){ cout<<*iter<<endl; } 对于list而言，只能采用迭代器的方式访问（思考一下他的实现原理，很容易理解为何只能这样访问）。
解题思路： 这种问题都可以采用快慢链表的方式来解决，两个链表相差n个元素，等快的链表到达链表尾部的时候，慢的位置就是需要删除的元素。 删除排序链表中的重复元素 II 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1:输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:输入: 1->1->1->2->3输出: 2->3 解题思路： 这里的关键点在于如何判定重复的节点，以及首节点就开始重复的情况 先说首节点开始重复的问题，这个需要用到头节点之前添加钩子节点的方法来解决。 重复节点的判断，循环遍历后续节点，直到出现不重复的节点位置，直接把重复节点之前的pre的下一个节点指向这个不同的节点即可。 环形链表 给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
移除重复节点 题目描述 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 l2 : l1); return head->next; } 面试题18. 删除链表的节点 题目描述 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 说明： 题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点 解题思路 删除链表的节点，其实就是重新更改next指针的指向，让其跳过要删除的节点即可 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 删除排序链表中的重复元素 题目描述 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
可以用哈希表 map 加速查询，即将每一项 target - num 作为 key，如果后面任何一个 num 作为 key 可以在 map 中找到，则得解，且上一个数的原始值可以存在 map 的 value 关于快慢指针，经典的题目有环形链表、删除有序数组中的重复项。 环形链表 环形链表是一道简单题，题目如下： 给定一个链表，判断链表中是否有环。 接下来终于说道快慢指针的另一种经典用法题型，删除有序数组中的重复项了。 删除有序数组中的重复项 删除有序数组中的重复项是一道简单题，题目如下： 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 这道题，要原地删除重复元素，并返回长度，所以只能用快慢指针。但怎么用呢？快多少慢多少？ 其实这道题快多少慢多少并不像前面题目一样预设好了，而是根据遇到的实际数字来判断。
但别人封装好了不代表我们就可以不关注了，数据结构作为程序员的内功心法，是非常值得我们多花时间去研究的，我这就翻开书复习复习： 本文就先从大家最经常使用的「 数组 」和「 链表 」聊起。 链表的访问 链表的优势并不在与访问，因为链表无法通过首地址和下标去计算出某一个节点的地址，所以链表中如果要查找某个节点，则需要一个节点一个节点的遍历，因此链表的访问时间复杂度为O(n) 链表的插入与删除 如果当前还未定位到指定的节点，只是拿到链表的Head，这个时候要去删除此链表中某个固定内容的节点，则需要先查找到那个节点，这个查找的动作又是一个遍历动作了，这个遍历查找的时间复杂度却是O(n)，两者加起来总的时间复杂度其实是 以“删除上图的E节点”为例，假如当前链表指针已经定位到了E节点，删除的时候，需要将这个E节点的前面一个节点H的后继指针改为指向A节点，那么E节点就会自动脱落了，但是当前链表指针是定位在E节点上，如何去改变 ，所以首先需要将下一个节点先临时保存起来，赋值到temp中，以备后续使用 ListNode temp = curr.next; //开始处理当前节点，将当前节点的指针指向前面一个节点
阅读本文大概需要：13 分钟 写在之前 自打刷题以来 ，有不少于 10 个小伙伴问及链表问题 。 「头指针」顾名思义，是指向链表第一个结点的指针，如果有头结点的话，那么就是指向头结点的指针。 ： 1 4 5 8 2 3 2.计算单链表的长度 在使用链表的时候，经常需要求表的长度，为此我们可以创建一个球表长的函数，这个函数就是从左到右扫描，遍历表中的所有结点并完成计数，时间复杂度为 O(n 只需要简单的将指针赋值为 None，就抛弃了链表原有的结点，Python 解释器的存储管理系统会自动回收不用的存储。 碰到这样的问题从哪个方面去思考，如何去做才是最重要的，只有学会了这些，你在日后碰到相关问题的时候就知道如何去下手。 我在上面每个操作的讲解中大多数给出了图，通过图来看解法题目了然。
数组的缺陷 数组的问题关键是在增加与删除元素的时候。 数组插入操作 假设现在我们定义了一个[A, B, C, E, F, G]的数组，然后我们要插入一个D到这个数组里面。 实现逻辑如下： 首先把指针3的值置空； 然后把D、E、F三个值往上移动一个位置； 最后在例如Java的数组语言中，我们需要把数组的长度减1即可； 具体的实现效果看下图： ? 链表的特性： 每一个元素有两个成员变量value值与next指针（指向下一个元素）； 每一个元素串在一起后与数组是非常相似的结构； 与数组不一样的就是每一个元素一般都要定义一个Class（类）：一般都叫一个 在Redis里面就使用了跳表。不过面试过程中并不会给大家出跳表的题目来写程序，所以我们只需要理解它的原理即可。 跳表的核心是为了优化链表元素随机访问的时间复杂度过高的问题 (O(n))。 2个结点； n/(2^h) = 2, 从这个公式我们可以求得 h = log2(n)-1； 所以最后得出跳表的时间复杂度是O(log n) 跳表查询的空间复杂度分析 首先原始链表长度为n 如果索引是每2
从最后一个元素向前遍历到第i个位置，分别将它们都向后移动一个位置； 将要插入元素填入位置i处； 表长加1； 2.删除算法思路： 如果删除位置不合理，抛出异常； 取出删除元素； 从删除元素位置开始遍历到最后一个元素位置 next=p->next;p->next=s; 返回成功 H.单链表的删除 1.单链表第i个数据删除结点的算法思路： 声明一个结点p指向链表第一个节点，初始化j从1开始 当j<i时，就遍历链表，让 若要频繁插入和删除时，宜采用单链表结构。 2.当线性表中的元素个数变化较大或者根本不知道有多大时，使用单链表。 L.静态链表 1.用数组来代替指针，来描述单链表。 2.如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些 D.栈的应用—递归 1.递归：一个直接调用自己或通过一系列的调用语句间接地调用自己的函数称为递归函数 2.每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。
从栈的操作特性来看，是一种 操作受限的线性表，只允许在一端插入和删除数据。 不包含任何元素的栈称为空栈。 栈也被用在编程语言的编译器和内存中保存变量、方法调用等，比如函数的调用栈。 特点 链表是通过指针将零散的内存块串连起来的。所以链表不支持 随机访问，如果要找特定的项，只能从头开始遍历，直到找到某个项。所以访问的时间复杂度为 O(n)。 高效的插入和删除。 所以，在链表中插入和删除一个数据是非常快速的，时间复杂度为 O(1)。 三种最常见的链表结构，它们分别是： 单链表 双向链表 循环链表 单链表 定义 ? 在单向链表中，如果迭代链表时错过了要找的元素，就需要回到链表起点，重新开始迭代。 在双向链表中，可以从任一节点，向前或向后迭代，这是双向链表的一个优点。 链表代码写得好坏，可以看出一个人写代码是否够细心，考虑问题是否全面，思维是否缜密。 所以，这也是很多面试官喜欢让人手写链表代码的原因。 一定要自己写代码实现一下，才有效果。 6.
-在队列开头删除或者恢复项 -请空队列 2.实现接口数据表示 一种可靠的方法是使用链表，相比于使用数组的好处是删除首项时不需要移动其余元素，只需重置头指针指向新的首元素即可 然而在链表中插入节点，只需给两个指针赋值。类似的，从链表中删除节点只需要重新设置一个指针并释放被删除节点占用的内存即可。 3.选择数据结构的思路 选择何种数据结构一般取决于具体的问题，如果因频繁地插入和删除项导致经常调整大小，而且不需要经常查找，选择链表更好。如果只是偶尔插入或删除项，但是经常进行查找，使用数组更好。 false : true; } 5.删除项 删除项是最复杂的任务，因为必须连接剩余的子树形成有效的树： 如果待删除的节点没有子节点（即叶子节点leaf）,这种情况下只需要将父节点中的指针重置为NULL 代码中用临时指针记录被删除节点的地址，被删除节点的父节点指针被重置后，程序会丢失被删除节点的地址。但是free()函数需要这个信息，所以先把指针的值存储在temp中。
3）链地址法（拉链法）：对于相同的哈希值，使用链表进行连接，再将链表的头指针存放在哈希表的对应单元中。 智能指针可以自动释放new分配的内存，不需要手动delete这些new分配的内存 智能指针的实质是一个对象，行为却表现的像一个指针 auto_ptr:c++98版本，在c++11中已不再使用，管理权转移的思想 ，若通过拷贝构造和赋值操作符赋值它们，原指针会变成null ，而 复制所得的指针将取得资源的唯一控制权。 特性：查找、删除、插入：理论上为O(1)，但是实际上要考虑碰撞的问题 底层数据结构为哈希表，解决冲突的策略使用的是拉链法，通过在不同桶中新建节点的方式来避免冲突 （3）容器适配器 在上述容器的接口上进行封装和改写实现 从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte. 10、map为何使用红黑树，而不用其他二叉树 对于STL中的set和map来说，需要进行频繁的插入和删除
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 注意： 此题对比原题有改动 示例 1: 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 复制代码 说明： 题目保证链表中节点的值互不相同 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点 本题很简单，解题思路如下： 因为被删除的节点可能为头节点，所以为了方便返回结果值 ，需要创建一个虚拟头节点 vhead 定义两个指针，pre 初始指向 vhead，next 初始指向 head next 不为空的时候，遍历链表 next.val = val 时，说明 next 指向节点为要删除的节点 ; } pre = pre.next; head = head.next; } }; 复制代码 至此我们就完成了 leetcode-剑指 Offer 18-删除链表的节点 如有任何问题或建议
为小游戏开发者提供单机、联机游戏完整的服务端实现方案，提供房间管理、帧同步、状态同步、云函数、云数据库等功能。
扫码关注云+社区
领取腾讯云代金券
云服务器
测试服务 WeTest
文件存储
云数据库 MongoDB
SSL 证书