C语言强化（七）链表相交问题_3 判断链表是否带环

/**
判断链表是否有环
node  链表头指针

方法：用两个指针，一个指针步长为1，一个指针步长为2，若最后相遇，则链表有环
有环 返回两指针相遇位置
无环 返回NULL
*/
ListNode * ifCircle(ListNode * node){
	if(NULL==node)
		return false;
	ListNode * fast = node;
	ListNode * slow = node;
	while(NULL!=fast&&NULL!=fast->nextNode){
		fast=fast->nextNode->nextNode;//步长为2
		slow=slow->nextNode;//步长为1
		if(fast==slow){
			cout<<"链表有环"<<endl;
			return fast;
		}
	}
	cout<<"链表无环"<<endl;
	return NULL;
}

#include <stdio.h>
#include<stdlib.h>
#include <iostream>


using namespace std;

/**
3.判断链表是否带环
思路
	方法：用两个指针，一个指针步长为1，一个指针步长为2，若最后相遇，则链表有环
	有环 返回两指针相遇位置
	无环 返回NULL
*/

/**
链表结构体
*/
struct ListNode{
	int data;
	ListNode * nextNode;
	ListNode(ListNode * node,int value){
		nextNode=node;
		data=value;
	}
};

ListNode * L1;


/**
判断链表是否有环
node  链表头指针

方法：用两个指针，一个指针步长为1，一个指针步长为2，若最后相遇，则链表有环
有环 返回两指针相遇位置
无环 返回NULL
*/
ListNode * ifCircle(ListNode * node){
	if(NULL==node)
		return false;
	ListNode * fast = node;
	ListNode * slow = node;
	while(NULL!=fast&&NULL!=fast->nextNode){
		fast=fast->nextNode->nextNode;//步长为2
		slow=slow->nextNode;//步长为1
		if(fast==slow){
			cout<<"链表有环"<<endl;
			return fast;
		}
	}
	cout<<"链表无环"<<endl;
	return NULL;
}

//创建无环链表
ListNode * createList(){
	ListNode * node = new ListNode(NULL,0);
	node = new ListNode(node,1);
	node = new ListNode(node,2);
	return node;
}

//创建有环链表
ListNode * createCircleList(){
	ListNode * node = new ListNode(NULL,0);
	ListNode * enter = node;
	node = new ListNode(node,1);
	node = new ListNode(node,2);
	enter->nextNode=node;
	node = new ListNode(node,3);
	node = new ListNode(node,4);
	return node;
}
void main()
{
	//L1=createList();
	L1=createCircleList();
	L1=ifCircle(L1);
	if(L1!=NULL)
		cout<<"两指针相遇结点为"<<L1->data<<endl;
	system("pause");
}