很多题目需要修改指针链接，如果操作不当，会造成链表结点的丢失，或者出现错误的回路。 我们早在 C/C++ 编程课上就学过链表数据结构。...这次循环将让 curr 的指针改为指向 prev，就将当前结点从后一半链表放进了前一半链表。 ? 循环开始时，prev 和 curr 分别指向链表的前半部分和后半部分 ?...将当前结点放入前一半链表 ? 下一轮循环时，prev 和 curr 仍然分别指向链表的前半部分和后半部分 而头结点的特殊情况是，全部链表都还未进行反转，即前一半链表为空。...总结 总结起来，我们解决这一类单链表问题时，遵循的步骤是： 判断问题是否为链表遍历-修改，套用链表遍历框架 思考单步操作，将代码加入遍历框架 检查指针丢失等细节 有很多更复杂的链表题目都以反转链表为基础...Two Numbers II[3] 以反转链表为基础解题 LeetCode 92 - Reverse Linked List II[4] 反转部分链表 希望本文的讲解能让你在写链表类题目时更得心应手。
题型一：反转单链表 思路解析 反转一个链表主要是想让第一个节点指向NULL，第二个节点指向第一个，以此类推。...那么定义一个循环后依此思路便可反转链表了。当然循环结束的条件为n3 == NULL，那么再仔细想一下，其实还有最后一个节点没有反转，此节点只需要最后单独反转便可。...那么为什么不让循环结束条件为n2 == NULL呢？是因为此时n3 == n2->next而n2又等于NULL，这就导致了错误。...还要一点需要注意的是：在解题前我们还要单独判断一下此链表是否为空。 图解如下： OJ题实例 LeetCode链接：206....} //最后一个节点的判断 n2->next=n1; return n2; } } 题型二：快慢指针 思路解析 通常快慢指针方法出现在需要找链表中间节点
⭐每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。...，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。...样例 输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL 思路 反转链表是一个经典题目 这里先判断头节点是否为空，或者仅存在一个节点，返回即可。...当不存在公共节点时，返回空节点。 数据范围 链表长度 [1,2000]。...循环条件为p->next是否存在 定义q = p -> next; 若q节点不是尾节点且p的指向与q的指向相同，即重复，跳过该节点。
【LeetCode #206】反转链表 反转一个单链表。...请判断一个链表是否为回文链表。...但是本题目中链表为单向链表，因此不可能从尾部开始遍历！ 但是一个显然的思路，可以将这个单向链表从中间截开，将其中一个进行反转，然后再进行判断。...解题思路： 首先两个链表的指针pA与pB一起走，并且其指向的地址都不同，循环一直下去到最后，必定有一个较短的链表指针（假设pA）为nullptr，将该指针指向较长链表的头部, pA=headB....接着继续向后移动，此时还有出现一次较长链表的指针为空的情况，将该指针指（pB）向较短链表的头部，pB=headA. 然后再一起向后移动，直到指向相同位置，跳出循环，并返回指针！
链表在面试中出现的频率很高，有的比较正常，考链表的常规操作，主要看基本功是否扎实，有些就比较难，难在思维的改变和是否能够想到对应的点。这里出现的是其中一个题目，我称之为有环链表问题。...也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。 首先来看最基本的这个问题：如何判断一个单链表是否存在循环，链表数目未知。算法不能破坏链表。...每遍历一个节点，都在这个结构中查找是否遍历过。如果找到有重复，则说明该链表存在循环。如果直到遍历结束，则说明链表不存在循环。...思路二：反转指针法 这种比较特别，是使用反转指针的方法，每过一个节点就把该节点的指针反向。当有环的时候，最后指针会定位到链表的头部，如果到最后，都没有再到头部，那说明链表不存在循环。...所以快慢指针无法解决链表存在循环的问题，快慢指针能解决的只是链表存在环的问题，也就是这个循环在链表尾部。可以说链表存在环是链表存在循环的一种特殊情况。
>next这里出现了问题。...也就是说在while循环里面即使cur->val==val我们还需要对prev是否为空分类讨论： 当prev为空，也就是第一个节点就是所需要删除的结点时： 最终的代码就是这样了： /** * Definition...牢牢地抓住开始，迭代和结束，我们不难写出下面的代码： n2所在的结点就是需要反转指向的结点，而结束标志就是没有需要反转指向的结点，也就是n2==NULL时结束。...=NULL; 另外1：链表判环问题 判断链表中是否有环 通过定义slow和fast指针，slow每走一步，fast走两步，若是有环，则一定会在环的某个结点处相遇（slow == fast）判断链表中是否有环...然后外部的for循环是指有多少个区间要反转， 内部的第1个循环是反转的过程，执行题单2-方法3，进行反转 内部的第2个循环是重新定位下一个cur的位置，然后进行迭代， 特别的，我自己加了一个头结点，对
▉ 算法思路 通过上边的问题分析，得出以下几种解决方法： ● 反转链表法 ● 栈实现 ● 递归实现 1、反转链表实现 从尾到头输出链表的内容，一般的思路就是将链表反转过来，然后从头到尾输出数据。...3、递归实现 可以通过递归的方式来实现单链表从尾到头依次输出，递归过程涉及到“递”和“归”，反转链表输出数据，正式利用了循环“递”的过程，所以数据先从头部输出，那么递归采用的是“归”的过程来输出内容，输出当前结点先要输出当前节点的下一节点...) 17 // 2、判断链表是否可反转(头节点是否为空、是否有第二个结点) 18 // 3、尾指针指向第一个结点的 next 19 // 4、尾指针向前移动 20 // 5、当前指针...this.head; //当前指针指向头节点 25 let pre = null;//尾指针 26 let next;//指向当前指针的下一个指针 27 28 //判断单链表是否符合反转的条件...2、重复计算：递归会出现很多的重复计算问题，重复计算对程序的性能有很大影响，导致消耗时间成指数增长，但是可以通过散列表的方式解决。
我们接下来进入到链表的部分。主要分为下面这几个主题: 反转链表 反转链表这里一共有三个题目供大家训练。分别是原地单链表的反转、两个一组反转链表和K个一组反转链表，难度由阶梯式上升。...而在面试当中凡是遇到链表，反转类的题目出现的频率也是数一数二的，因此把它当做链表开篇的训练类型，希望大家能引起足够的重视?。 No.1 简单的反转链表 反转一个单链表。...具体来说: 当 head 节点为空时，我们已经处理，通过✅ 当链表只包含一个节点时, 此时我们希望直接返回这个节点，对上述代码而言，进入循环后 pre 被赋值为cur，也就是head，没毛病，通过✅ 运行在...给定一个链表，判断链表中是否形成环。 思路 思路一: 循环一遍，用 Set 数据结构保存节点，利用节点的内存地址来进行判重，如果同样的节点走过两次，则表明已经形成了环。...求链表中间节点 判断回文链表 请判断一个单链表是否为回文链表。
题目描述 请判断一个链表是否为回文链表。...因为单链表不像字符串可以进行直接访问，所以这里采用的方式为，找到单链表中间元素，并反转单链表前半部分，然后与单链表后半部分进行比较是否为回文结构。...，第一个 while 循环中找到链表中间节点，并逐步反转链表节点，查找中间节点的方式为快慢两个指针，当快指针为空时，慢指针指向中间节点。...第一个循环结束后，left 为前半部分反转链表的头结点，slow 为后半部分链表的头结点，因为链表中节点个数为奇数时，slow 为中心节点，不需要参与回文判断，所以第一个循环后，加 if 判断。...第二个循环中判断 left 和 slow 两个链表的数据值是否一致。
因此只需要循环 size - k 次，找到新链表头部，然后进行指针的交换。最后返回新链表头即可。 注意：这道题虽然是旋转链表，但是实际上并没有真正的进行结点的移动，只是进行了指针的交换。...因为后半段需要反过来插入，因此我们可以对后半段链表进行反转，然后再按顺序插入到前半段链表就行。链表反转可以参考 Leetcode 【Linked List】206....Add Two Numbers II），都可以先将链表反转，然后再操作，这样就不用使用额外空间了。...add(-3)}，当计算到 -2 位置时，前缀和为 3 + (-1) = 1，前缀和 1 之前在 Hash Table 中出现过，因此需要将 add(1) 的下一个地址指向 -2 的下一个地址 add(...因此，不仅前缀和要在之前出现过，而且前缀和地址不是 discard 中删除的地址，才可以进行删除。如果不这样做，当碰到 add(5) 时，前缀和为 6，又要删除，从而造成错误的结果。
示例: 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5 思路分析: 在宏观视角看递归这篇文章中...当remainNum与k相等时，变量nextHead指向的节点及其之后的所有节点就是除去前K个节点之后剩余的链表。...subList = reverseKGroup(nextHead,k); } 细心的你应该注意到，在这里有一个问题，那就是如果剩余的节点个数小于K，那么上述代码中的while循环内nextHead=nextHead.next...就会出现空指针的问题。...prev; } 今天的分享就到这里了 如有错误 欢迎在公众号后台留言指出 下一篇我们将学习新的内容，敬请期待
由于是用连续内存空间存储的，那么就会出现，明明还剩50M内存，但由于不是连续的，而导致在创建一个大小为50M的数组时，申请内存失败。 那有没有一种数据结构是不需要占用连续的内存空间的呢？...文章内容主要包括以下几点： 什么是链表 单链表的基本操作：增、删、改、查 LeetCode #206 反转单列表 循环链表及LeetCode #141 环形链表检测 双向链表及其增加删除操作 01 什么是链表...比如，我们要判断链表中是否包含元素2，那么当变量cur指向下图的结点时，就可以判定链表中包含元素2。 ?...判断链表中是否包含某个元素的值时间复杂度分析： 要判断链表中是否包含某个元素，只能从头遍历链表，然后拿当前考察的结点数据域的值和目标值比对，因此时间复杂度整体上是O(n)； 03 通过单链表反转 来看如何写出正确的链表代码...对于这种尾结点的后继指针指向头结点的单链表，我们称之为循环链表。 接着看下LeetCode#141环形链表检测这个问题，题目描述如下： 给定一个链表，判断链表中是否有环。
单链表的遍历方向单一，只能从链头一直遍历到链尾。它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。...循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示： ?...，返回是否成功； offerFirst(E e)：头部插入元素，返回是否成功； offerLast(E e)：尾部插入元素，返回是否成功。...链表常见笔试题 链表最常见的笔试题就是链表的反转了，之前的文章《链表反转的两种实现方法，后一种击败了100%的用户！》...实现方法 3：循环 我们也可以通过循环的方式来实现链表反转，只是这种方法无需重复调用自身方法，只需要一个循环就搞定了，实现代码如下： class Solution { public ListNode
可以避免检查空链表，极大简化代码，减少错误的发生。可参见下面的题目。 套路二：双指针。单链表的快慢指针，要么设置两个指针指向不同的位置，要么设置两个指针走的步数不一样。 链表常考题目 1....反转链表 """ # 反转一个单链表。...简单版：两两反转链表 3....如果空间不是问题，最简单的方法是从头开始通过下一个字段探索节点，并将访问的节点存储在哈希表中-仅当我们访问哈希表中已经存在的节点时，存在一个循环。...当且仅当两个指针相遇时，列表才具有循环。 原因如下：如果快指针跳过了慢指针，则在下一步中，慢指针将等于快指针。
； 专业打假：其实这种说法是错误的，因为结点的数据域为char类型的且链表长度大于127的时候就会溢出，所以这种说法是错误的。...pos位置是尾结点且链表是循环链表就可以，但是如果是循环链表的话就没必要使用替换法删除pos位置的结点. 4-1.变式 如果要在pos位置之前插入一个结点，时间复杂度为O(1),也可以采用这种方法...prev 第三步：遍历判断两个链表是否值相等 反转过程是最重要的部分，这里给出一点图理解一下 class PalindromeList { public: bool chkPalindrome...，从前往后和从后往前读都是一样的 第一步：拷贝原链表，得到头指针copyhead 第二步：将原链表整体反转,得到r头指针eversehead 第三步：遍历判断两个链表是否值相等 （备注：这里一定一定要记得先拷贝一份原链表...，否则反转后得到的链表将不再是原先那个链表！）
前言 反转链表是程序员必备的基本素养，经常在面试、笔试的过程中出现。...一直觉得反转链表实现代码不是很好理解，决定搬leetcode那道经典反转链表题出来，用十多张图去解析它，希望加深大家对链表反转的理解，谢谢阅读。...leetcode的反转链表原题&答案 题目描述： 反转一个单链表。...5 curr.next = prev; // 6 prev = curr; //7 curr = nextTemp; //8 } 循环部分是链表反转的核心部分...这时候prev指向的就是链表的反转呀，所以第9行执行完，反转链表功能实现： return prev; //9 参考与感谢 LeetCode 官网
并且链表插入、删除时间复杂度为O(1)，而随机访问时间复杂度是O(n)。 循环链表与双向链表 循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。...单链表的尾结点指针指向空地址，表示这就是最后的结点了，但是循环链表的尾结点指针是指向链表的头结点； 双向链表：单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。...如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致内存不足出现（out of memory）。如果声明的数组过小，则可能出现不够用的情况。...这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时； 链表本身没有大小的限制，并且支持动态扩容； 单链表操作 反转 方法一：递归反转法，在反转当前节点之前先反转后续节点。...这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
当任务能够被相似的子任务定义时，采用递归处理十分有效。二分排序和遍历等问题往往有简洁的递归解决方案。...递归函数的格式 if (判断是否是基础情况) { return 该基础情况下的函数的值 } else if (判断是否为另一种基础情况) { return 该基础情况下的函数的值...createLinkedList(data.subList(1,data.size())); firstNode.setNext(headOfSublist); return firstNode; } eg:反转链表...最后思考的特殊情况 if(head == null || head.getNext() == null){ return head; } //一般情况 假如他可以反转链表得到出去第一个的剩下反转...定义循环不定式，并在循环体每次结束后保持循环不变式 先一般，后特殊 每次必须向前推进循环不变式中涉及的变量值 每次推进的规模必须为1 eg：依然是上面的链表反转的例子，用循环不定式实现 public
经过上面的两步循环，成功的将指针进行了反转，剩下的节点循环也就如出一辙了。 ? 当循环到最后节点【5】时，下个节点为null，此时结束while循环，而节点【5】也是指向了上一个节点【4】。 ?...最后将两个链表进行判断是否是一样的。...debug开始循环后，fast直接走到链表的第3个节点【2】 ? slow.next就是链表的后半部分，再将后半部分进行链表反转 最后我们也就得到如下2个链表。 ?...当快指针指向节点【5】时，slow慢节点指向节点【3】 注意：中间省略了一步，即慢指针指向节点【2】时，快指针指向节点【4】 节点【5】是最后一个节点，再次进入while循环。 ?...最后一次循环时，慢指针指向了4，快指针下一个节点已经为null，此时结束循环。 ? 五，移除重复节点 ?
数据结构 关于什么是链表，本文不做过多介绍，不了解的小伙伴自行去充能 稍微带大家回顾下链表的分类，不做过多介绍，直接看图 单链表 双向链表 循环链表 单向循环链表 ...双向循环链表 环形链表 由单链表 + 单向循环链表组成 花式玩法 后续的场景都会基于某些特定类型的链表，大家不要太放飞自我 我也会在各个场景中明确指明基于那个类型，大家不要看偏了... 单向节点 OneWayNode 虽然代码用 java 实现，但涉及到的算法实现是通用的，希望大家不要被开发语言所禁锢 链表反转 基本上指的是单链表的反转，大家就认为是单链表的反转...；但面试时，往往会对时间复杂度或空间复杂度做一个极致的考量 这道题如果出现在面试中，那么考核点就是：时间复杂度 O(N) ，额外空间复杂度 O(1) ，那么你们觉得递归的实现会让面试官满意吗？ ... 除了有限几个变量，没有使用额外的空间，那么额外空间复杂度就是 O(1) 入环节点 给定一个单向链表（单链表或环形链表中的某一种），判断它是否成环，不成环返回 null ，成环则返回入环的第一个节点
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
