判断单链表是否是循环链表以及找出循环链表入口

#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;


struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
	vector<int> postorderTraversal(TreeNode *root) {
		vector<int> res;
		if (!root){
			return res;
		}

		stack<TreeNode*> s;

		int sign = 1;
		TreeNode* p = NULL;

		do{
			while (root){
				//printf("val :%d in stack\n", root->val);
				s.push(root);
				root = root->left;
			}

			p = NULL;
			sign = 1;
			while (!s.empty() && sign){
				root = s.top();

				if (root->right == p){
					res.push_back(root->val);
					p = root;
					s.pop();
				}
				else{
					sign = 0;
					root = root->right;
				}
			}
		} while (!s.empty());

		return res;
	}

	vector<int> preorderTraversal(TreeNode *root) {
		vector<int> res;
		if (!root){
			return res;
		}

		stack<TreeNode*> s;
		bool flag = false;

		do{
			while (root){
				s.push(root);
				root = root->left;
			}

			flag = false;

			while (!s.empty()){
				root = s.top();
				s.pop();

				printf("%d ", root->val);

				if (root->right)
				{
					root = root->right;
					flag = true;

					break;
				}
				 
			}
		} while (!s.empty() || flag);

		printf("\n");

		return res;
	}

	vector<int> midorderTraversal(TreeNode *root) {
		vector<int> res;
		if (!root){
			return res;
		}

		queue<TreeNode*> s;

		do{
			if (!s.empty())
			{
				root = s.front();
				s.pop();
			}
			
			if(root){
				printf("%d ", root->val);

				if (root->left)
				{
					s.push(root->left);
				}
				if (root->right)
				{
					s.push(root->right);
				}
			}

		} while (!s.empty());

		printf("\n");

		return res;
	}
};

class node
{
public:
	char c;
	char d;

	double i;

	short s;

}no;

class A

{

	int i;

	char c1;

};

class B:public A

{

	char c2;

};

class C:public B

{

	char c3;

};

struct LinkList{
	int val;
	LinkList* next;
	LinkList(int val):val(val){
		next = NULL;
	}
};
typedef LinkList ListNode;

void doseq(LinkList* node){
	if (!node)
	{
		return;
	}
	
	LinkList* head = node;

	LinkList* slow = head;
	LinkList* quick = head;

	while (quick)
	{
		quick = quick->next;

		if (quick)
		{
			quick = quick->next;
			slow = slow->next;
		}
	}
	
	LinkList* cur = NULL;
	stack<LinkList*> q;
	LinkList* next = slow->next;
	slow->next = NULL;
	cur = next;
	while (cur)
	{
		q.push(cur);
		next = cur->next;
		cur->next = NULL;
		cur = next;
	}
	
	cur = head;

	LinkList* cucur = NULL;
	while (!q.empty() && cur)
	{
		next = q.top();
		q.pop();

		cucur = cur->next;

		next->next = cur->next;
		cur->next = next;

		cur = cucur;
	}
}

LinkList* insert(LinkList* node, int val){
	while(node->next)
	{
		node = node->next;
	}

	LinkList* newnode = new LinkList(val);
	node->next = newnode;

	return newnode;
}

void print(LinkList* q)
{
	while (q)
	{
		printf("%d ", q->val);
		q = q->next;
	}
	
}

bool hasCycle(ListNode *head) {
	if (!head)
	{
		return false;
	}

	ListNode* slow = head;
	ListNode* quick = head;

	while (quick)
	{
		quick = quick->next;

		if (quick)
		{
			quick = quick->next;
			slow = slow->next;

			if (quick == slow)
			{
				break;
			}
		}
	}

	slow = head;
	while(slow != quick)
	{
		slow = slow->next;
		quick = quick->next;
	}

	//printf("cycle begin node:%d\n", slow->val);

	return false;
}
int main(){
	LinkList* q1 = new LinkList(1);
	insert(q1, 2);
	insert(q1, 3);
	insert(q1, 4);
	LinkList* q2 = insert(q1, 5);
	q2->next = q1;
	
	
	printf("%res:%d\n", hasCycle(q1));
}

判断循环链表很简单，就是快慢两个指针；

但是如何找循环链表入口就需要分析下， 看下面的图：

假设quick,slow指针在Z点相遇，则slow走了a+b;quick走了a+b+c+b；

因为quick速度是slow的2倍，有(a+b)/t * 2 = (a+2b+c);

也就是a=c

这个结论很给力，此时qucik、slow在Z点，而我们现在想到循环入口Y点，头结点到Y点需要a步，而a=c，z再到y是c，所以此时从x,z点走当二者相遇就是Y点了。

就是这样。

判断单链表是否是循环链表以及找出循环链表入口,布布扣,bubuko.com

判断单链表是否是循环链表以及找出循环链表入口

原文：http://blog.csdn.net/boyxiaolong/article/details/22281777