网站后台被百度蜘蛛抓取,北京工商注册官网,使用cdn的网站,网站服务器维护技术在链表中#xff0c;不光只有普通的单链表。之前写过的的一个约瑟夫环形链表是尾直接连向头的。这里的环形链表是从尾节点的next指针连向这链表的任意位置。 那么给定一个链表#xff0c;判断这个链表是否带环。qj题141.环形链表就是一个这样的题目。 这里的思路是用快慢指… 在链表中不光只有普通的单链表。之前写过的的一个约瑟夫环形链表是尾直接连向头的。这里的环形链表是从尾节点的next指针连向这链表的任意位置。 那么给定一个链表判断这个链表是否带环。qj题141.环形链表就是一个这样的题目。 这里的思路是用快慢指针慢指针一次走一步快指针一次走两步。两个指针都从起始位置出发带环就一定会相遇否则快指针率先走到链表的末尾。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slowhead,*fasthead;while(fast fast-next){slowslow-next;fastfast-next-next;if(slowfast){return true;}}return false;
}那么这里有两个问题。 1、为什么快指针走两步慢指针走一步就一定会相遇。 2、快指针一次走3步、4步…n步可以吗? 1、为什么快指针走两步慢指针走一步就一定会相遇 又可能在慢指针刚入环时就和快指针相遇了。慢指针叫slow快指针叫fast假设slow进环时fast与slow的距离为N时这里fast走两个slow走一个。 N-21 N-1 N-42 N-2 N-63 N-3 也就是说每追及一次距离就缩小1当距离为0时就追上了。 2、快指针一次走3步、4步…n步可以吗? 假设slow进环时fast与slow的距离时N。fast走3个slow走1个。 N N-2 N-4 这里要思考一下如果N为偶数或奇数是否有不同 当N为偶数时假设N为44-2为2 4-4为0这时就追上了。 当N为奇数时假设N为53 1 -1这时就错过了进行新一轮的追击。 这时候fast和slow的距离就变成了c-1c为环的长度。 当c-1为偶数的时候下一轮就追不上。 当c-1为奇数时下一轮就追的上。 c-1为偶数时之所以能追上是因为当fast和slow都走起来时相对位移是2所以为偶数时下一轮就追上了。 这里总结一下 N时偶数第一轮就追上了。 N时奇数第一轮就会错过距离变成c-1。 如果c-1为偶数的时候下一轮就追上了。 如果c-1为奇数的时候永远也追不上。 同时存在N为奇数且C时偶数那么就永远追不上。 真的永远追不上吗 假设从初始位置到进入环的距离为Lfast与slow的距离为N。环的长度为N。 slow走的距离为L fast走的距离为LnCC-N 不确定fast是否只走不到一圈也可能走了好几圈所以用nC。
fast走的距离是slow的三倍 3LLxCC-N 2*Lx1*C-N
当2L为偶数的时候x1偶数C-偶数N时2L才为偶数。 当2L为奇数的时候x1奇数C-奇数N时2L才为奇数。 N是奇数时C也是奇数 N是偶数时C也是偶数 反证出N为奇数且C为偶数不能同时存在永远追不上的条件不成立。所以上面的结论不成立。
正确结论 一定能追上。 N为偶数第一轮就追上了。 N为奇数第一轮追不上第二轮C-1为偶数时就追上了
