判断链表是否有环

//判断一个单向链表是否有环
//思路：设置双指针，一快一慢，若有环两个指针一定相遇
//       快指针pf每次走一步，以便于遍历所有结点
//       慢指针ps每次走两步，目的是遍历环中的每一个结点
#include 
using namespace std;

//链表结点
typedef struct ListNode
{
	struct ListNode* next;
}ListNode;

bool loopList(ListNode* head)
{
	ListNode* pf = head;
	ListNode* ps = head;
	if (pf == NULL || pf->next == NULL)
	{
		return false;
	}
	pf = pf->next->next;
	while (pf != ps)
	{
		//pf每次走两步，所以判断pf和pf的下一个节点是否为NULL
		if (pf == NULL || pf->next == NULL)
		{
			return false;
		}
		pf = pf->next->next;
		ps = ps->next;
	}
	return true;
}

int main()
{
	ListNode* node1 = new ListNode;
	ListNode* node2 = new ListNode;
	ListNode* node3 = new ListNode;
	ListNode* node4 = new ListNode;
	ListNode* node5 = new ListNode;
	ListNode* node6 = new ListNode;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = node6;
	//node6->next = NULL;
	node6->next = node3;
	bool ret = loopList(node1);
	if (ret)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	system("pause");
	return 0;
}