leetcode每日一题链表有环无环链表长度求解

1.链表有无环

采用快慢指针求解，指针slow和fast从链表头开始走，slow每次往后走一步，fast每次往后走两步，若链表有环则俩指针必定在环内相遇 

2.有环链表长度

如图所示，假设slow和fast在Pos处第一次相遇，join为环的入口，假设从表头Head到Join有l个节点，join沿逆时针到Pos有x个节点，环中有R个节点，显然fast走过的节点数是slow的两倍，那么有

                                                                                               （1）

其中为一任意正整数，可以推出 

                                                                                                                 （2）

让fast和slow从Pos开始继续沿着逆时针走，同时用另外个指针p沿着Head一次走一步，到第二次相遇时fast比slow多走了一圈，而fast的速度刚好是slow的两倍，则slow刚好走了一圈，记下此时slow走过的节点数可以得到环内包含的节点数，根据（2）可以得到，若slow从Pos走过 时刚好到达Join而此时p也刚好到达Join，记录下此时head走过的节点数，则链表的长度为

代码

struct Node {int data;Node* next;
};Node* IsCycle(Node *head)
{Node* slow = head;Node* fast = head;while (true) {if (fast == nullptr || slow == nullptr) {return nullptr;}slow = slow->next;fast = fast->next;if (fast == nullptr) {return nullptr;}fast = fast->next;if (fast == slow) {return fast;}}
}int LenList(Node* head)
{Node* Pos = IsCycle(head);if (Pos == nullptr) {return LenNonCycle(head);}int l = 0;int r = 0;bool rget = false;bool lget = false;Node* slow = Pos;Node* fast = Pos;Node* p = head;while(true) {slow = slow->next;if (!rget) {++r;}if (!lget) {++l;}fast = fast->next->next;if (fast == slow) {rget = true;}if (slow == p) {lget == true;}if (rget && lget) {return r + l;}}
}