在线学习软件开发网站建设,中国建设银行网站首页怎么销户,3yx这个网站做刷单,门户网站建设自评报告1.判断是否带环#xff1a;
用快慢指针 slow指针一次走一步#xff0c;fast指针一次走两步 当两个指针相遇时#xff0c;链表带环#xff1b;两个指针不能相遇时#xff0c;当fast走到倒数第一个节点或为空时#xff0c;跳出循环返回空指针。
那么slow指针一次走一步
用快慢指针 slow指针一次走一步fast指针一次走两步 当两个指针相遇时链表带环两个指针不能相遇时当fast走到倒数第一个节点或为空时跳出循环返回空指针。
那么slow指针一次走一步fast指针一次走两步是否一定能追上呢 fast永远比slow快一步所以两者之间每走一次举例减少 1 即 N-1,N-2,N-3…0
那么fast一次走三步slow一次走一步呢
2.找第一个入环节点 假设环的节点数为C环之外的节点数是L 这里可以分为三种情况 N是偶数——slow走第一圈追上 N是奇数C-1是偶数——一定能追上 N是奇数C-1是奇数呢
推导 3LLn*C-N 2Ln * C-N 若 C为偶数N为奇数那么 n * C-N 不会是偶数 所以 N是奇数C-1是奇数的情况不存在 结论 slow走1步fast走3步时一定能追上
3.代码实现
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slowhead;struct ListNode* fasthead;struct ListNode* meetNULL;while(fast!NULLfast-next!NULL){slowslow-next;fastfast-next-next;if(slowfast){meetslow;goto next;}}return NULL;next:struct ListNode* curhead;while(cur!meet){curcur-next;meetmeet-next;}return meet;
}
