环形链表理解||QJ141.环形链表

在链表中，不光只有普通的单链表。之前写过的的一个约瑟夫环形链表是尾直接连向头的。这里的环形链表是从尾节点的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* slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}

那么这里有两个问题。
1、为什么快指针走两步，慢指针走一步就一定会相遇。
2、快指针一次走3步、4步…n步可以吗?

1、为什么快指针走两步，慢指针走一步就一定会相遇
又可能在慢指针刚入环时就和快指针相遇了。慢指针叫slow，快指针叫fast，假设slow进环时，fast与slow的距离为N时，这里fast走两个slow走一个。
N-2+1 N-1
N-4+2 N-2
N-6+3 N-3
也就是说每追及一次，距离就缩小1，当距离为0时就追上了。

2、快指针一次走3步、4步…n步可以吗?

假设slow进环时，fast与slow的距离时N。fast走3个slow走1个。
N
N-2
N-4
这里要思考一下，如果N为偶数或奇数是否有不同？
当N为偶数时，假设N为4，4-2为2 4-4为0这时就追上了。
当N为奇数时，假设N为5，3 1 -1这时就错过了，进行新一轮的追击。
这时候fast和slow的距离就变成了c-1，c为环的长度。
当c-1为偶数的时候，下一轮就追不上。
当c-1为奇数时下一轮就追的上。
c-1为偶数时之所以能追上，是因为当fast和slow都走起来时相对位移是2，所以为偶数时下一轮就追上了。
这里总结一下：
N时偶数，第一轮就追上了。
N时奇数，第一轮就会错过，距离变成c-1。
如果c-1为偶数的时候，下一轮就追上了。
如果c-1为奇数的时候，永远也追不上。
同时存在N为奇数且C时偶数，那么就永远追不上。

真的永远追不上吗？

假设从初始位置到进入环的距离为L，fast与slow的距离为N。环的长度为N。
slow走的距离为：L
fast走的距离为：L+nC+C-N
不确定fast是否只走不到一圈，也可能走了好几圈所以用nC。

fast走的距离是slow的三倍
3L=L+xC+C-N
2*L=（x+1）*C-N

当2L为偶数的时候，（x+1）偶数C-偶数N时，2L才为偶数。
当2L为奇数的时候，（x+1）奇数C-奇数N时，2L才为奇数。
N是奇数时，C也是奇数
N是偶数时，C也是偶数
反证出，N为奇数且C为偶数不能同时存在，永远追不上的条件不成立。所以上面的结论不成立。

正确结论：
一定能追上。
N为偶数第一轮就追上了。
N为奇数第一轮追不上，第二轮C-1为偶数时就追上了