【链表】判断链表是否有环-快慢指针_判断链表是否存在环快慢指针

目录

一、思想

二、代码

三、运行结果

一、思想

什么叫有环？

        一个结点有两个指向的时候就会产生环。例如在一个单链表0-9的数据中，3的下个节点为4，让3的下个结点同时指向9，此时就会在3的位置产生两条路，一个指向9，一个指向4，这就是有环的情况。

快慢指针求解：

• 慢指针一次走一次
• 快指针一次走两次
• 如果有环，快指针会在环里转圈圈，慢指针也会在某时刻进入环内，两指针相遇。；没有环，快指针会优先走到空NULL。
• 如果有环-->快慢指针迟早会相遇

空不能作为循环条件，如果有环，快慢指针会在环内，永远不会到达空的位置，会陷入死循环。

二、代码

#include <assert.h>
#include<stdio.h>
 
    typedef struct Node
    {
        int data;
        struct Node* next;
    }Node, * List;
 
 
	//初始化
	void   InitList(List plist)
	{
		assert(plist != NULL);
		if (plist == NULL)
		{
			return;
		}
 
		//plist->data;//头节点的data不使用
		plist->next = NULL;
	}
//尾插
	bool   Insert_tail(List plist, int val)
	{
		assert(plist != NULL);
		if (plist == NULL)
		{
			return false;
		}
 
		//申请结点
		Node* p = (Node*)malloc(sizeof(Node));
		assert(p != NULL);
		//将数据val放入到新结点;
		p->data = val;
		//找尾巴
		Node* q;
		for (q = plist; q->next != NULL; q = q->next)
		{
			;
		}
		//插入新结点,把p插入到q的后面
		p->next = q->next;//p->next=NULL;
		q->next = p;
		return true;
	}
	//在plist查找第一个key值,找到返回结点地址,没有找到返回NULL;
	Node* Search(List plist, int key)
	{
		assert(plist != NULL);
		if (plist == NULL)
		{
			return NULL;
		}
 
		for (Node* p = plist->next; p != NULL; p = p->next)
		{
			if (p->data == key)
			{
				return p;
			}
		}
		return NULL;
	}
 
 
bool IsCircle(List plist)
{
	assert(plist != NULL);
	if (plist == NULL ||plist->next==NULL)
	{
		return false;
	}
	Node* p = plist->next;//慢指针,一次走一步
	Node* q = plist->next->next;//快指针,一次走两步;
 
	while (q != NULL && q->next!=NULL)
	{
		if (p == q)
		{
			break;
		}
		p = p->next;
		q = q->next->next;
	}
 
	if (q == NULL || q->next == NULL)
	{
		return false;
	}
	else
	{
		return true;
	}
}
 
//输出
	void  Show(List plist)
	{
		assert(plist != NULL);
		if (plist == NULL)
		{
			return;
		}
		for (Node* p = plist->next; p != NULL; p = p->next)
		{
			printf("%d   ", p->data);
		}
		printf("\n");
	}
 
int main()
{
	Node head;
	InitList(&head);
//测试数据一：无环情况
	for (int i = 0; i < 10; i++)
	{
		Insert_tail(&head, i);
	}
	Show(&head);
	if (IsCircle(&head))
	{
		printf("该链表有环!\n");
	}
	else
	{
		printf("该链表没有环!\n");
	}
//测试数据二：让3的下个结点指向9=》有环情况
	Node* q = Search(&head, 3);
	Node* s = Search(&head, 9);
	s->next = q;//构造环
 
	if (IsCircle(&head))
	{
		printf("该链表有环!\n");
	}
	else
	{
		printf("该链表没有环!\n");
	}
	return 0;
}

三、运行结果

0-9的第一批数据：无环

让3的下个结点指向9，构造有环的第二批数据：有环