学步园

链表中环的入口位置

这是一个老生长谈的问题了，具体解释可以看我的另一篇博客：判断链表中是否有环
----- 有关单链表中环的问题， 下面直接给出AC代码，以及测试用的代码：

#include <iostream>
#include <string>
using namespace std ;


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

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head) return NULL ;

		ListNode *fast = head;
		ListNode *slow = head ;

		//判断是否有环
		while (fast != NULL && fast->next != NULL)
		{
			slow = slow->next ;
			fast = fast->next->next ;
			if (fast == slow)
				break ;
		}
		//没有环
		if (fast == NULL || fast->next == NULL)
			return NULL ;

		//有环，找到入口点
		ListNode *p0 = head ;
		while (p0 != slow)
		{
			p0 = p0->next ;
			slow = slow->next ;
		}

		return p0 ;
    }
};

int main(int argc, char **argv)
{
	ListNode *head = NULL ;
	ListNode *tail = NULL ;
	int tmp ;
	int count = 0 ;
	int k = 5 ; //表示第k个节点是入口节点
	ListNode *niNode = NULL ;
	while(cin >> tmp)
	{
		count ++ ;
		ListNode *tmpNode = new ListNode(tmp) ;
		if(head == NULL)
		{
			head = tail = tmpNode ;
		}
		else
		{
			tail->next = tmpNode ;
			tail = tail->next ;
		}

		if (count == k)
			niNode = tail ;
	}

	tail = head ;
	while (tail->next != NULL)
	{
		cout << tail->val << " " ;
		tail = tail->next ;
	}
	cout << tail->val ;
	cout << endl;

	tail->next = niNode ;

	Solution s ;

	ListNode *ret = s.detectCycle(head) ;
	if (ret != NULL)
		cout <<"入口节点是：" << ret->val << endl;
	else
		cout << "不存在环" << endl;

	return 0 ;
}

输入：1 2 3 4 5 6 7 8 9 10

运行结果：

1 2 3 4 5 6 7 8 9 10
入口节点是：5
请按任意键继续. . .

实现思路不多说了，和上面的完全一样，直接上代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
         if (!head) return false ;

		ListNode *fast = head;
		ListNode *slow = head ;

		//判断是否有环
		while (fast != NULL && fast->next != NULL)
		{
			slow = slow->next ;
			fast = fast->next->next ;
			if (fast == slow)
				return true ;
		}
		
		return false ;
    }
};