判断单链表是否带环？若带环，求环的长度？求环的入口点

本文主要是介绍判断单链表是否带环？若带环，求环的长度？求环的入口点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题一：如何判断链表是否带环？

思路：利用快慢指针，定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走的快的指针追上了走的慢的指针，那么链表就包含环；如果走的快的指针走到了链表的末尾都没有追上另一个指针，那么链表就不包含环。

 //判断单链表是否带环？
ListNode* ListIsCircle(ListNode* first)
{if (first == NULL) {return NULL;}ListNode* fast = first;ListNode* slow = first;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {//相遇，有环return fast;}}//fast走到结尾，证明没有环return NULL;
}

问题二：若带环，求环的长度

思路：如果有环，通过上面的方法可以得到快慢指针的相遇点，记作pos, 从pos出发，每走一步，计数器加一，再次回到该点，计数器的值就是环的长度

int ListLength(ListNode* first)
{if (first == NULL) {return 0;}ListNode* cur = ListIsCircle(first);ListNode* fast = cur;ListNode* slow = cur;int count = 0;while (1) {slow = slow->next;fast = fast->next->next;count++;if (slow == fast)break;}return count;
}

问题三：求环的入口点

思路：有两种方法，方法一：利用一个结论：从链表头结点到入口节点的长度 = 相遇节点到入口节点的长度

结论证明：设环的长度为：C
从链表头结点到入口节点的长度为:L
入口节点到相遇节点的长度为：X
快指针在环中走的圈数：n
快指针走的步数是：L+nC+X
慢指针走的步数是：L+X
根据快指针走的步数是慢指针的两倍可得关系：L+nC+X = 2(L+X) 化简后可得：nC = L+X

ListNode* FindLoopPort(ListNode* first) {if (first == NULL) {return NULL;}ListNode* cur = ListIsCircle(first);assert(cur);ListNode* tmp = first;while (cur != tmp) {cur = cur->next;tmp = tmp->next;}return cur;
}

方法二：只写了思路，还是利用快慢指针，先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动，当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。

//测试
void TestCircle()
{ListNode* first = NULL;ListPushBack(&first, 1);ListPushBack(&first, 2);ListPushBack(&first, 3);ListPushBack(&first, 4);ListPushBack(&first, 5);ListPushBack(&first, 6);ListPushBack(&first, 7);ListNode* cur = first;while (cur->next != NULL) {cur = cur->next;}ListNode* tmp = FindTailK(first, 4);cur->next = tmp;ListNode* res = ListIsCircle(first);printf("%d ", res->data);int a = ListLength(first);printf("%d ", a);ListNode* node = FindLoopPort(first);printf("%d ", node->data);
}