怎么做网站引流,wordpress游客评论游客,大连哪家网站建设好,建站宝盒里的手机网站1.链表的带环问题 上图就是一个典型的带环链表 1.1如何判读链表是否带环#xff1f; 最常见的方法就是利用快慢指针#xff0c;快指针追加慢指针#xff0c;当二者相等的时候即可判断链表带环
其实现的代码如下#xff1a; bool hasCycle(struct ListNode*head) { s…1.链表的带环问题 上图就是一个典型的带环链表 1.1如何判读链表是否带环 最常见的方法就是利用快慢指针快指针追加慢指针当二者相等的时候即可判断链表带环
其实现的代码如下 bool hasCycle(struct ListNode*head) { struct ListNode* slow head,*fast head; while(fast fast-next) { slow slow-next; fast fast -next-next; if(slow fast) return true; } return false; } 1.2 为什么快慢指针一定会相遇 1.2.1 两指针每走一步其距离缩小1 假设slow进环的时候fast与其的距离为N此时每当slow走一步fast与slow的距离都会缩小1,最后缩小到0从而两指针相遇。 1.2.2 两指针每走一步其距离缩小2
初步证明 1.N是偶数第一轮就追上。 2.N是奇数第一轮就会错过距离变成C-1C为环的长度。 a.如果C-1是偶数下一轮就追上了 b.如果C-1是奇数那么就永远追不上
深度证明 假设slow进环时fast跟slow的距离为N slow走的距离是L fast走的距离Lx*CC-N slow进环时假设fast已经在环里转了x圈 如果fast走的距离是slow的3倍 3*L Lx*C C-N 2*L (x1)*C-N 偶数 x1)*偶数-奇数 所以只有两种情况 N是奇数C也是奇数 N是偶数时C也是偶数 由此可以得出N是奇数且C是偶数不能同时存在在初步证明中的永远追不上不成立 把两种情况代入初步证明中可以得出结论 结论一定能追上 N偶数第一轮就追上了 N是奇数第一轮追不上C-1是偶数第二轮就追上 1.3 找环的入口点 1.3.1 方法一
一个指针从头结点开始前进而slow指针在与fast相遇点开始前进,当head指针和slow指针相遇的时候该点为环的入口点。
证明如下 相遇时
slow走的路程L N
fast走的路程Lx*CN
fast走的路程是slow的2倍化简后的公式为L x*C-N - L (x-1)*C C - N
以下为代码的实现 struct ListNode*meet slow; while(meet ! head) { meet meet -next; head head -next; } return meet; 1.3.2 方法二 newhead meet-next; newhead NULL;
通过上述两个操作让找环入口点转化为找两个链表的交点问题
