如何建设微信商城网站,微商做网站,深圳网站seo优化排名公司,网站预订系统建设文章目录前言环形链表环形链表 II写在最后前言 本章的OJ练习相对于OJ练习(4)较为简单。不过#xff0c;本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。 对于OJ练习(4)#xff1a;- 传送门 -#xff0c;分割链表以一种类似于归并的思想解得本章的OJ最重要的是要我们证明为何可以这么做。这也是面试中常出现的。 对于OJ练习(4)- 传送门 -分割链表以一种类似于归并的思想解得回文链表以一种巧妙复用前面OJ题的思想解得。 啰嗦一下对于本章最重要的是需要证明为什么这样做可以所以我们不光要做出来OJ还要能够理解并自行给出证明。 环形链表 题目链接 - 传送门 -。 题目描述给你一个链表的头节点 head 判断链表中是否有环。如果链表中存在环 则返回 true 。 否则返回 false 。
带环链表类似于下面这种结构 是否有环实际上就是链表的最后一个节点是否指向了链表其中的一个节点如果有环我们遍历一遍链表的话会陷入死循环。那么我们该如何判断链表是否有环呢
解题思路 由于带环链表直接遍历会陷入死循环也就是说会无限在环内遍历下去因此这里可以引出一个追击问题用快慢指针遍历链表。 我们定义两个指针分别是慢指针slow快指针fast这两个指针同时遍历链表slow每次走一步fast每次走两步。fast会先进入环然后在环内跑圈当slow进入环后这就是一个典型的追及问题了slow每次在环内走一步fast每次在环内走两步两个指针的距离每次缩小1最终fast会追上slow与slow指向同一节点。当两个指针相等时就可以判断该链表带环因此判断条件就是fast slow (return true)。 如果链表不带环fast最终会指向NULL的前一个结点或者就指向NULL。因此整个判断过程就结束了。 可以看到如果链表没有环链表的结点个数为偶数时fast是指向NULL结束链表的节点个数为奇数时fast是指向最后一个结点结束。
解题代码
bool hasCycle(struct ListNode *head) {struct ListNode* fast head, * slow head;while (fast fast-next){fast fast-next-next;slow slow-next;if (fast slow) return true;}return false;
}为什么快慢指针可以 快指针每次走两步慢指针每次走一步当两个指针都在环内的时候就成了一个追击问题两个指针的距离每次缩小一最终快指针会追上慢指针因此判断其有环。 那假如快指针每次走三步慢指针走一步呢
我们将带环链表抽象成下图 假设每次快指针走三步慢指针每次走一步当两个指针都进环后此时的相对位置为 我们记此时慢指针slow与快指针fast的距离为N慢指针每次走一步快指针每次走三步因此N每次减少2于是就有 N - 2 N - 4 N - 6 N - 8 ..... 最终有两种情况 . N 1然后再减2 - -1 . N 2然后再减2 - 0 如果N最后减为-1那么再次追击如果N最后减为0则快指针等于慢指针判断为true。所以得出当N为奇数时追不上当N为偶数时一定追得上。 如果追不上最后fast会在slow的下一个位置然后继续追击那么继续追击又是否追的上呢
我们假设环的长度为C那么此时再次追击两个指针的距离就为C - 1,令T C - 1,则 T - 2 T - 4 T - 6 T - 8 ..... 最终有两种情况 . T 1然后再减2 - -1 . T 2然后再减2 - 0 因此这里又有两种情况有了前面的推导这里不难得出当C为偶数时则C - 1T为奇数此时继续追不上并且下一次也是一样所以这里会陷入死循环当C为奇数时则C - 1为偶数此时是追的上的。因此当C为偶数时永远追不上当C为奇数时追的上。
所以通过以上分析快指针每次走三步慢指针每次走一步不一定能判断是否为带环链表可能会陷入死循环尽管陷入死循环就说明带环。 那么快指针每次走4步走5步走n步呢这里就不是我们该探讨的范围了相信大家心里已经有答案了。 环形链表 II 题目链接- 传送门 -。 题目描述给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。注意不允许修改链表。 与上一题不同的是这一题首先是要判断链表是否带环然后在带环的基础上返回链表入环的第一个节点。类似于下图 解题思路
这里直接说做法先以第一题的思路使用快慢指针找到快指针和慢指针相遇的那个点然后一个指针从该点开始走一个指针从头开始走每次走一步最终两个指针会在入环的第一个节点相遇然后返回这个节点。
解题代码
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *slow head, *fast head;while (fast fast-next){// 快指针每次走两步fast fast-next-next;// 慢指针每次走一步slow slow-next;// 如果找到相遇的那个点就开始找入环的第一个节点if (slow fast){struct ListNode *cur slow;// 一个从头开始走一个从当前节点开始走while (cur ! head){head head-next;cur cur-next;}// 最终相遇的那个点就是入环的第一个节点return cur;}}// 如果链表不带环就返回NULLreturn NULL;
}证明为什么一个指针从快慢指针相遇的那个点开始走一个指针从头开始走最终两个指针会在入环的第一个节点处相遇
假设快慢指针在pos位置相遇设链表头到入环的第一个节点的距离为X 入环的第一个节点到pos的距离为Ypos到入环的第一个节点的距离为L整个环的周长为C 由此我们计算一下当快慢指针在pos相遇时分别走了多长的距离 快指针X nC Y; 慢指针X Y; 为什么快指针有个nC而不是C 为什么慢指针没有C? 快指针有个nC是因为有可能这个环的长度比较短在慢指针入环时快指针已经在环内走了n圈了。慢指针没有C是因为慢指针入环后最多只会走C - 1步不可能出现在环内步数超过一圈的情况因此慢指针没有C。
因此由快指针每次走两步慢指针每次走一步的特点可以得出下面这个公式
X nC Y 2(X Y);
化简得
X nC - Y;
进一步化简得
X (n - 1)C (C - Y);
最终得
X (n - 1)C L; 由此公式当一个指针从pos开始走他走了(n - 1)C最终还是会在pos位置。而当(n - 1)C走完后从头开始走的指针与入环的第一个节点的距离为L与此时pos到入环的第一个节点的距离相等。因此为什么这样的做法可以以上就是答案。 写在最后 对于单链表的题目练习最重要的是思路我们在数据结构阶段要养成画图的习惯因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。 感谢阅读本小白的博客错误的地方请严厉指出噢
