Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

HideTags

 Linked List Two Pointers

#pragma once
#include<iostream>
using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};


bool hasCycle(ListNode *head) {
	ListNode* p1 = head;
	ListNode* p2 = head;
	while (p1&&p2)
	{
		p1 = p1->next;
		p2 = p2->next;
		if (p2)
			p2 = p2->next;
		else
			return false;//到头，一定无环
		if (p1 == p2)
			return true;
	}
	return false;
}

void main()
{
	ListNode* l1 = new ListNode(1);
	ListNode* l2 = new ListNode(2);
	ListNode* l3 = new ListNode(3);
	ListNode* l4 = new ListNode(4);
	ListNode* l5 = new ListNode(4);
	l1->next = l2;
	l2->next = l3;
	//l3->next = l1;
	l4->next = l1;
	cout << hasCycle(l1) << endl;
	/*cout << hasCycle(l2) << endl;
	cout << hasCycle(l3) << endl;
	cout << hasCycle(l4) << endl;
	cout << hasCycle(l5) << endl;
	cout << hasCycle(l5->next) << endl;*/
	system("pause");

}

141.Linked List Cycle