typedef struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
}ListNode;
class Solution {
public:
//链表中是否有环
bool hasCycle(ListNode* head) {
if(!head) {
return false;
}
ListNode* fast=head;
ListNode* slow=head;
while(fast&&fast->next) {
slow=slow->next;
fast=fast->next->next;
if(fast==slow) {
return true;
}
}
return false;
}
//链表中环的起始点
ListNode *beginCycle(ListNode* head) {
if(!head) return nullptr;
ListNode *fast = head;
ListNode *slow = head;
while(fast&& fast->next) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
//从相遇点和链表起始点同时循环两个指针，直到二者相遇，相遇点就是环起始点
ListNode *first = head;
while(first != slow) {
first = first->next;
slow = slow->next;
}
return first;
}
}
return NULL;
}
//链表中环的长度
int lengthCycle(ListNode* head) {
if(!head) {
return false;
}
ListNode* fast=head;
ListNode* slow=head;
while(fast&&fast->next) {
slow=slow->next;
fast=fast->next->next;
if(fast==slow) {
slow=slow->next;
int length=1;
while(slow!=fast) {
slow=slow->next;
length++;
}
return length;
}
}
return 0;
}
};
void TestListCycle() {
ListNode lp1(1);
ListNode lp2(2);
ListNode lp3(3);
ListNode lp4(4);
ListNode lp5(5);
ListNode lp6(6);
ListNode lp7(7);
ListNode lp8(8);
ListNode lp9(9);
lp1.next=&lp2;
lp2.next=&lp3;
lp3.next=&lp4;
lp4.next=&lp5;
lp5.next=&lp6;
lp6.next=&lp7;
lp7.next=&lp8;
lp8.next=&lp9;
lp9.next=&lp3;
ListNode* head=&lp1;
Solution s;
std::cout<<"hasCycle:"<<s.hasCycle(head)<<std::endl;
ListNode* lp=nullptr;
lp=s.beginCycle(head);
std::cout<<"detectCycle:"<<lp->val<<std::endl;
std::cout<<"lengthCycle:"<<s.lengthCycle(head)<<std::endl;
}
转载于:https://www.cnblogs.com/smallredness/p/11301868.html
