房地产微网站建设栏目设计,忘记网站备案账号,网站开发设计思路文档,html网站开发工具下载博主ID#xff1a;代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表#xff08;2#xff09; 环形链表
先来看看环形链表的原题#xff1a; 中间的部分叙述有点繁杂#xff0c;简单来概括就是#xff0c;假如有一个节点#xff0c…博主ID代码小豪 文章目录 环形链表环形链表的性质分析快慢指针法指针的追及相遇问题 环形链表2 环形链表
先来看看环形链表的原题 中间的部分叙述有点繁杂简单来概括就是假如有一个节点如果一直调用该节点的next最后会回到该节点那么这个链表就是带环的。
环形链表的性质分析
假如有个cur指针从头开始遍历链表如果这个链表不是环形链表那么这个cur指针会遍历至NULL指针处 那么让一个指针从头开始遍历整个链表如果这个指针到了NULL就说明这个链表不是环形链表。 while (cur){cur cur-next;}return false;但是如果这个链表是环形链表该如何证明呢因为环形链表中是不在空节点的NULL。如果cur一直遍历那么迭代就会进入死循环
解决思路就是在环形链表当中加入一个标志指针让这个指针处于环形处。 这样子让cur指针继续遍历链表最后一定会遇上flag指针证明这个链表是环形链表
快慢指针法
那么问题来了如何让flag指针处于环内呢因为如果计算机知道flag处于什么位置是环内我又何必写一大堆代码证明这个链表是环形链表呢而且如果这个链表不带环那么flag又应该在什么位置呢
为了解决这个问题我们可以设置两个指针指向第一个节点一个是快指针fast一个是慢指针slow让快指针一次递进多个节点而慢指针依次递进一个节点让这个操作进行循环。
如此操作会发生两种情况 情况1链表为非带环链表fast指针来到空节点处NULL返回false 情况2链表为带环链表fast指针会一直循环遍历环形链表。slow一定会进入环内。 fast会在链表内循环遍历所以fast有可能会和slow重合如果fast和slow重合了就说明这个链表是环形链表。
指针的追及相遇问题
通过前面前面分析可知如果该链表是环形链表那么快指针就有可能在环内与慢指针相遇那么会不会发生快慢指针不会相遇的情况呢
首先快指针一定是比慢指针移动更快的我们假设快指针每次移动两个节点慢指针每次移动一个节点。
我们假设现在有一个环形链表这个链表的入口点为点P。
设慢指针来到入口p时快指针与慢指针的距离为N 慢指针走一步快指针会走两步因此这两个指针的距离会随着执行次数每次减一慢指针的走1步快指针的会走2步那么快指针相距慢指针就近了一步。
次数距离0N1N-12N-2依此类推N-22N-11N0
可以发现如果快指针走两步慢指针走一步那么这两个指针一定会在环中相遇。
那么如果快指针一次移动三个节点慢指针一次移动一个节点我们能得出什么样的结论呢
还是假设当慢指针到达入口点距离快指针的距离为N 当慢指针与快指针的距离N为偶数时
次数 距离0N1N-22N-4依次类推N/2-12N/20
当N为偶数时快慢指针会相遇
当快指针与慢指针之间的距离为奇数时
次数 距离0N1N-22N-4依次类推N/2-11N/2-1
可以发现快指针会越过慢指针此时快指针会比慢指针多一个节点左右的距离快指针需要再次遍历整个环形链表直到与慢指针相遇。 设环形链表的周长为C那么此时快指针与慢指针的距离为C-1.
当C为奇数时C-1为偶数
那么程序的运行次数与快慢指针的距离关系为
次数 距离0C-11C-32C-5依次类推(C-1)/2-12(C-1)/20
由此推出当N为奇数C为奇数时快指针最后会追上慢指针。
当C为偶数时C-1为奇数
次数 距离0C-11C-32C-5依次类推(C-1)/2-11(C-1)/2-1
可以发现快指针和慢指针的距离在这一次追及之后快慢指针的距离又回到了C-1。所以当N为奇数C为偶数C-1为奇数时快指针走三个节点慢指针走1个节点的方式会永远不会相遇。
综上所述如果我们想用快慢指针相遇的方式证明环形链表最好的方法是让快指针一次后进两个节点而慢指针一次后进一个节点。
当快指针后进多个大于等于2的节点时有可能会出现快慢指针永远无法相遇的情况。比如当快指针后进3个节点时如果此时N为奇数C为偶数时快指针永远无法与慢指针相遇从而导致死循环的出现
解题代码如下
bool hasCycle(struct ListNode *head) {if(headNULL)return false;struct ListNode*slowhead;struct ListNode*fasthead-next;while(fast){if(fast-nextNULL)return false;fastfast-next-next;slowslow-next;if(fastslow)return true;}return false;
}环形链表2 这是前面环形链表的变形体这个OJ的要求是这样的假设这是一个环形链表那么就要找到这个链表的入口节点并将这个节点返回。如果是非环形链表则返回NULL指针。
首先我们将这个问题的实现分为两个部分第一、我们要先确定这是一个环形链表然后我们求出这个环形链表的入口点。
确定环形链表的方法已经说明过了现在要思考的是如何找到这个入口点。
我们首先来思考一下快慢指针的位移关系已知快指针的速度是慢指针的两倍因此当慢指针来到入口点L时快指针已经移动2L了。
我们假设从链表头到入口点的距离为L从入口点到达相遇点的距离为N环形链表的周长为C。
如果LC。假如slow移动了L的距离来到入口点可以知道fast移动距离为2L在圈内循环了x圈x至少为1 当slow来到相遇点时那么slow移动的距离是LN而fast移动的距离为LNx1C。
如果LC。假如slow移动了L的距离来到入口点可以知道fast移动距离为2L在圈内循环了0圈 当slow来到相遇点时那么slow移动的距离是LN而fast移动的距离为LNC。
根据fast的位移是slow的两倍可以得出 当LC时2LNLNx1C。 当LC时2LNLNC。
可以合并成一个公式 2LNLNyC。y1.
合并同类项得LyC-N。 我们可以图中明显的看出一个关系
如果一个指针从相遇点移动YC-N个节点时会来到入口点。而且一个指针从链表头开始移动L位时回来到入口点。 并且LyC-N。
可以得出如果让一个指针从链表头开始移动一个指针从相遇点开始移动。这两个指针会在入口点相遇。
代码如下
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fasthead;struct ListNode*slowhead;while(fast){if(fast-nextNULL)return NULL;fastfast-next-next;slowslow-next;if(fastslow){struct ListNode*meetslow;while(meet!head){meetmeet-next;headhead-next;} return meet;}}return NULL;
}
