查看网站注册信息,网站开发工具中的三剑客,简单网站系统,做商业地产常用的网站#x1f308;图示指向任意节点的带环链表
如图#xff1a;
#x1f308;快慢指针法判断链表是否带环
#x1f31f;思路#xff1a;快指针fast一次走2步#xff0c;慢指针slow一次走1步#xff0c;fast先进环在换中运动#xff0c;随后slow进入环。两指针每同时移动…图示指向任意节点的带环链表
如图
快慢指针法判断链表是否带环
思路快指针fast一次走2步慢指针slow一次走1步fast先进环在换中运动随后slow进入环。两指针每同时移动一次二者的相对距离减少1此时二者一定会在环中相遇。 同时还可得出结论相遇时slow不可能走过一整个环。相同时间内fast走过的路程是slow的二倍fast和slow相遇时slow一定不可能走过了一整个环假设slow走过了一次整个环则fast走过了两次环在这期间二者一定会相遇因此假设不成立。 图示fast和slow相遇过程
拓展思考快指针fast一次走3步慢指针slow一次走1步此时一定会相遇吗C是圆环长度 答不一定当C-1为奇数时永远不会相遇。slow进环后每同时移动一次二者距离缩小2。当fast在slow后面且相隔1个节点时再移动一次变成了fast在slow前且相隔1节点进入了新一轮追逐追逐距离还是是C-1注意追逐距离不是C-2而C-1是奇数时不管怎么减2都不可能减为0只会从1减到-1又进入新一轮循环追逐距离还是C-1奇数陷入死循环。
根据原理类推fast一次走4步slow一次走一步每次距离缩小3。当环的周长C为3的倍数时会相遇C的长度模3余2时陷入死循环循环时每轮追击距离为C-1当环的周长模3余1时陷入死循环循环时每轮追击距离为C-2。
找到带环链表中环的起始点
由上文得出结论fast和slow相遇时slow不可能走过一整个环但是fast在slow进环前可能已经在环里走了好多圈了。此时fast大概率走了n-1圈但还没有走够n圈当然巧合情况是fast刚好走了n圈但是在fast追slow的过程中一定会把n圈补齐。 想象一个L非常大C非常小的带环链表如下图 公式推导 假设起点到入口点长度L 假设环的周长C 假设入口点到相遇点的数据X fast与slow相遇时: slow走过的总长度LXfast走过的总长度Ln ∗ * ∗cX 列出方程 2(LX)Ln ∗ * ∗CX ⇒ LXn ∗ * ∗C ⇒ Ln ∗ * ∗C-X 具象说明一个指针从起点走另一个指针从相遇点走它们会在入口点相遇
☀️OJ题1判断链表是否带环
链接: https://leetcode.cn/problems/linked-list-cycle/description/
思路fast一次走两步slow一次走一步若有环则两指针一定会相遇。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode*fasthead,*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(slowfast)return slow;}return NULL;
}☀️OJ题2返回入环节点
链接: https://leetcode.cn/problems/linked-list-cycle-ii/description/
法一公式法 Ln ∗ * ∗C-X。
先让fast和slow相遇再让一个指针从相遇点走另一个指针从头节点走两指针相遇点即为入环节点。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slowhead,*fasthead,*meet;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){meetfast;while(meet!head){meetmeet-next;headhead-next;}return head;}}return NULL;
}法二切断环交叉链表求交点。
先让fast和slow相遇从相遇点出断开环此时演变为交叉链表求交点问题先让长链表走差距步再同时走相遇处即环的起点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*fasthead,*slowhead,*meet,*meetnext;struct ListNode*head1,*head2;int count10,count20;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){meetslow;meetnextmeet-next;meet-nextNULL;head1head;head2meetnext;while(head1){head1head1-next;count1;}while(head2){head2head2-next;count2;}int subcount1-count2;head1head;head2meetnext;if(sub0){while(sub--){head1head1-next;}}else if(sub0){;}else{while(sub){head2head2-next;}}while(head1!head2){head1head1-next;head2head2-next;}return head1;}}return NULL;
}
