算法面试题：如何判断单链表中是否存在环

深碍√TFBOYSˉ_ 2022-06-02 12:44 161阅读 0赞

## 题目分析 ##

**一道算法面试题：判断单链表是否存在环**。

我们知道单链表中结点都是一个结点指向下一个结点这样一个一个链接起来的，直到尾结点的指针域没有指向，单链表就到此结束了。

这里存在环的意思就是，尾结点的指针域并为空，而是指向此单链表的其他结点，这样就形成环了，这样遍历单链表就死循环了因为破坏了结束条件。

**前面我们算法面试题 [快速找到单链表中间节点][Link 1] 所用的快慢指针，同样可以用来判断是否存在环，如果存在环的，快慢指针一定会相遇**。

当然可以用其他方法，不过这种方法比较容易想到和比较容易理解，今天我们来讲解这种方法。**注意下面的单链表是带头结点的单链表**。

![SouthEast][]

## 人为构造有环的单链表 ##

**很简单，将正常的单链表的尾结点的next指针域指向单链表的其他结点**。

看代码：

//loop_pos 设置环结点的位置
    Status SetLoopLinkList(LinkList list,int loop_pos)
    {
    	if (list == NULL|| LengthLinkList(list) == 0 || loop_pos >= LengthLinkList(list))
    	{
    		return ERROR;
    	}
    	//头结点
    	Node* node =  list;
    	//第loop_pos个结点
    	Node* loop_node = NULL;
    	int i = 0;
    	while (1)
    	{
    
    		if (node->next != NULL)
    		{
    			node = node->next;
    			i++;
    			if (i == loop_pos)
    			{
    				loop_node = node;
    			}
    		}
    		else
    		{
    			break;
    		}
    	}
    	//将尾结点指向链表中其他结点
    	node->next = loop_node;
    	return OK;
    }

看一下设置环的单链表的展示情况：

展示单链表的信息会环的位置一直循环

![SouthEast 1][]

## 快慢指针判断单链表是否环 ##

看代码：

/*
    使用快慢指针判断单链表是否存在环。
    使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，
    若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。
    list 带头结点的单链表
    返回值 >0:存在环返回环的位置	0:不存在环
    */
    int IsLoopLinkList(LinkList list)
    {
    	//空指针
    	if (list == NULL)
    	{
    		return 0;
    	}
    	//只有头结点,没有元素
    	if (list->next == NULL)
    	{
    		return 0;
    	}
    	Node* slow = list;
    	Node* fast = list;
    	int loc = 0;
    	while (1)
    	{
    		if (fast->next == NULL)
    		{
    			//快指针 到底链表尾结点说明 没有环，此时slow 指向中间结点
    			return 0;
    		}
    		else
    		{
    			if (fast->next != NULL && fast->next->next != NULL)
    			{
    				fast = fast->next->next;
    				slow = slow->next;
    			}
    			else
    			{
    				fast = fast->next;
    			}
    		}
    		//某个时刻 快慢指针相遇，说明此处存在环！
    		if (slow == fast)
    		{
    			return (slow - list) / sizeof(Node);
    		}
    
    	}
    	return 0;
    }

**那么问题来了，既然知道该单链表是代码单链表，那么我怎样将其还原为正常单链表呢？**

## 带环单链表去掉环 ##

**我们只需要将尾结点的next指针域置为NULL就还原为正常单链表了**。我们怎样找到尾结点呢？请看代码。

/*
    去掉单链表中的环，将尾结点的next域置位空。
    环位置结点之后的结点，判断其next域是否为环结点，如果是环节点，说明是尾结点
    */
    Status ClearLoopLinkList(LinkList list)
    {
    	int loopLoc = IsLoopLinkList(list);//环结点位置
    	Node* node = list;
    	Node* loop = NULL;
    	if (loopLoc)
    	{
    		int num = 0;
    
    		while (node->next != NULL)
    		{
    			node = node->next;
    			num++;
    			if (num == loopLoc)
    			{
    				loop = node;
    			}
    			if (num > loopLoc && node->next == loop)
    			{
    				//找到尾结点，尾结点指针域置位空
    				node->next = NULL;
    				break;
    			}
    		}
    	}
    	return OK;
    }

## 最后验证结果 ##

我们测试下，人为设置环，判断单链表是否有环，做清除环，看遍历是否正常。

![SouthEast 2][]

一切操作正常。

## 所有代码 ##

在之间单链表的算法实现基础上做的，代码有点多，做了下分文件。

### LinkList.h ###

#pragma once
    #ifndef __LINK_LIST_H__
    #define __LINK_LIST_H__
    #define	ERROR 0
    #define OK 1
    typedef int EleType;
    typedef int Status;
    typedef struct Node Node;
    
    //链表元素
    struct Node
    {
    	EleType data;//数据域
    	Node * next;//指针域
    };
    //带头结点的单链表
    typedef Node* LinkList;
    void PrintLinkList(LinkList list);
    /*
    创建拥有头结点的链表
    头插法创建链表，往链表中添加元素，新创建的的元素始终在头结点后面类似 头指针 -> 头结点->An->An-1->An-2 ...-> A1
    元素的数据 随机生成100以内的数字
    */
    Status CreatLinkListInHead(LinkList *list, int n);
    
    //尾插法创建链表，往链表中添加元素，先添加的元素放前面，后添加的元素放后面，遵循先来后到的道理
    Status CreatLinkListInTail(LinkList *list, int n);
    
    //获取链表元素数据,通过指针返回 链表第position个元素的 数据，position从1开始
    Status GetELement(LinkList list, int position, EleType *e);
    
    //往链表中第position位置 插入元素，元素数据为 e，元素位置从1开始数
    Status InsertLinkList(LinkList *list, int position, EleType e);
    
    //在链表第position位置 删除元素，通过指针返回 删除元素的数据内容
    Status DelLinkListEle(LinkList *list, int position, EleType *e);
    
    //清空整个链表，释放指针指向的内存
    Status FreeLinkList(LinkList *list);
    
    //获取单链表元素个数
    int LengthLinkList(LinkList list);
    
    /*
    给单链表设置环，尾结点 next域本应该指向NULL，让其指向链表中的其他元素，使之形成有环的单链表。
    list：单链表
    loop_pos：形成环的位置，也就是尾指针指向单链表中的第几个结点
    */
    Status SetLoopLinkList(LinkList list,int loop_pos);
    
    /*
    将去掉单链表中的环
    */
    Status ClearLoopLinkList(LinkList list);
    #endif // !__LINK_LIST_H__

### LinkList.c ###

#include <stdio.h>
    #include <Windows.h>
    #include "LinkList.h"
    void PrintLinkList(LinkList list) {
    	if (NULL ==list) {//链表为空
    		printf("printLinkList error \n");
    		return;
    	}
    	int i = 1;
    	LinkList li = list->next;//从头结点后面第一个结点开始遍历
    	while (li)//最后一个元素没有指向，不会进行循环。
    	{
    		printf("第%d元素:%d\t", i, li->data);
    		li = li->next;
    		if (i % 5 == 0)
    		{
    			printf("\n");
    			Sleep(3000);
    		}
    		i++;
    		
    	}
    	printf("\n");
    	return;
    }
    //创建拥有头结点的链表
    //头插法创建链表，往链表中添加元素，新创建的的元素始终在头结点后面类似 头指针 -> 头结点->An->An-1->An-2 ...-> A1
    //元素的数据 随机生成100以内的数字
    Status CreatLinkListInHead(LinkList *list,int n) {
    	srand(time(0));//设置随机种子，为产生随机数做准备。
    	//LinkList 类型 和 Node * 类型是一样的！看最上方定义类型别名，为什么可以做呢？链表的头指针 就是指向结点Node，所有链表类型是 Node *，只是为了更好看而已。 
    	LinkList li=NULL;
    	Node *node=NULL;//可以定义为 LinkList *node = NULL;
    	int i = 0;
    	li = (LinkList)malloc(sizeof(Node));//头指针指向头结点，给头结点分配空间
    	if (NULL == li||n<0) {//分配内存空间失败或者链表元素个数非法 返回
    		return ERROR;
    	}
    	li->next = NULL;//初始头结点没有指向
    	for ( i = 0; i < n; i++)
    	{
    		node = (Node*)malloc(sizeof(Node));//给结点分配空间
    		if (NULL==node) {//给分配空间失败 
    			return ERROR;
    		}
    		node->data = rand()%100;//除以100取余的到100以内的数字，不包括100，如果含100 就需要+1
    		node->next = li->next;//新添加的元素指针域 指向头结点后面的结点
    		li->next = node;//头结点指针域 指向新增加的元素
    
    	}
    	*list = li;//通过指针 给外部链表赋值
    	return OK;
    }
    //尾插法创建链表，往链表中添加元素，先添加的元素放前面，后添加的元素放后面，遵循先来后到的道理
    Status CreatLinkListInTail(LinkList *list, int n) {
    	srand(time(0));//设置随机种子
    	LinkList li = NULL ;
    	Node *node = NULL;
    	int i = 0;
    	li = (LinkList)malloc(sizeof(Node));
    	if (NULL == li || n<0) {//分配内存空间失败或元素个数非法
    		return ERROR;
    	}
    	li->next = NULL;//初始头结点指向
    	*list = li;//给通过外部链表赋值，指向头结点，此时 list 和 li 都指向头结点。
    	for ( i = 0; i < n; i++)
    	{
    		node = (Node*)malloc(sizeof(Node));//给结点分配空间
    		if (NULL == node) {//分配空间失败 
    			return ERROR;
    		}
    		node->data = rand() % 100;//除以100取余的到100以内的数字，不包括100，如果含100 就需要+1
    		li->next = node;//新结点 放到链表末尾
    		li = node;//移动链表指针指向最新链表最后一个元素，为了下次循环在链表末尾添加元素
    		//temp = node;
    	}
    	//最后表尾元素指针域 设置NULL
    	li->next = NULL;
    	//*list = li;//一定要放在for循环前面，不然头结点的内存空间没有指向！起初l指向头结点，但是进入for循环后l的指向发生改变要移动指向最新添加的结点元素。
    	return OK;
    }
    //获取链表元素数据,通过指针返回 链表第position个元素的 数据,position从1开始
    Status GetELement(LinkList list, int position,EleType *e) {
    	//异常情况：空指针,元素位置非法
    	if (NULL == list || position < 1) {
    		return ERROR;
    	}
    	LinkList li = list;
    	int i = 1;
    	while (li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围，都遍历完链表还没找到元素。
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	*e = li->next->data;
    	return OK;
    }
    //往链表中第position位置 插入元素，元素数据为 e,元素位置从1开始数
    Status InsertLinkList(LinkList *list,int position,EleType e) {
    	Node *node = (Node*)malloc(sizeof(Node));
    	//异常情况：空指针，为插入元素分配空间失败，元素位置非法，
    	if (NULL == list || NULL==node || position < 1) {
    		return ERROR;
    	}
    	LinkList li = * list;
    	int i = 1;
    	while ( li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	node->data = e;
    	node->next = li->next;//让 插入结点指针域指向 原来位置的结点
    	li->next = node;//让插入结点位置前的结点 指向插入结点
    	return OK;
    }
    //在链表第position位置 删除元素，通过指针返回 删除元素的数据内容
    Status DelLinkListEle(LinkList *list, int position, EleType *e) {
    	//异常情况：空指针,元素位置非法
    	if (NULL == list || position < 1) {
    		return ERROR;
    	}
    	LinkList li = *list;
    	Node * node = NULL;
    	int i = 1;
    	while (li && i<position) {//在链表范围内遍历元素 直到 找到第position位置的 元素  
    		i++;
    		li = li->next;
    	}
    	if (NULL == li || position > i) {//超出链表范围，都遍历完链表还没找到元素。
    		return ERROR;
    	}
    	//通上面 while循环 当i = position 跳出循环 ，li 此时指向链表 第position位置的 前面一个结点。
    	node = li->next;//保存要删除元素的地址
    	li->next = node->next;//让删除元素前置结点 指向 删除元素 直接后继结点。然后就可以释放 删除结点的空间了。
    	*e = node->data;//将删除元素数据通过指针修改返回
    	free(node);//释放删除元素空间
    	return OK;
    }
    //清空整个链表，释放指针指向的内存
    Status FreeLinkList(LinkList *list) {
    	if (NULL == list)//空指针
    		return ERROR;
    	//注意：头结点不要释放！只释放头结点后面的结点元素
    	//LinkList li = *list;这样将会把头结点也释放掉
    	LinkList li = (*list)->next;//将链表指针指向第一个结点元素，从这个元素开始释放
    	Node * node = NULL;//临时变量，指向还未释放的元素
    	while (li){//链表指针向移动指向结点元素，直到没有后继结点
    		node = li->next;//保存要释放结点 的直接后继结点位置。 
    		free(li);
    		li = node;//继续指向 未释放结点
    	}
    	//将头结点指针域设置为NULL
    	(*list)->next = NULL;
    	return OK;
    }
    //获取单链表元素个数
    int LengthLinkList(LinkList list)
    {
    	Node* node = list;
    	if (node == NULL)
    	{
    		return 0;
    	}
    	if (node->next == NULL)
    	{
    		return 0;
    	}
    	int length = 0;
    	while (node->next!=NULL)
    	{
    		length++;
    		node = node->next;
    	}
    	return length;
    }
    //loop_pos 设置环结点的位置
    Status SetLoopLinkList(LinkList list,int loop_pos)
    {
    	if (list == NULL|| LengthLinkList(list) == 0 || loop_pos >= LengthLinkList(list))
    	{
    		return ERROR;
    	}
    	//头结点
    	Node* node =  list;
    	//第loop_pos个结点
    	Node* loop_node = NULL;
    	int i = 0;
    	while (1)
    	{
    
    		if (node->next != NULL)
    		{
    			node = node->next;
    			i++;
    			if (i == loop_pos)
    			{
    				loop_node = node;
    			}
    		}
    		else
    		{
    			break;
    		}
    	}
    	//将尾结点指向链表中其他结点
    	node->next = loop_node;
    	return OK;
    }
    /*
    使用快慢指针判断单链表是否存在环。
    使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，
    若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。
    list 带头结点的单链表
    返回值 >0:存在环返回环的位置	0:不存在环
    */
    int IsLoopLinkList(LinkList list)
    {
    	//空指针
    	if (list == NULL)
    	{
    		return 0;
    	}
    	//只有头结点,没有元素
    	if (list->next == NULL)
    	{
    		return 0;
    	}
    	Node* slow = list;
    	Node* fast = list;
    	int loc = 0;
    	while (1)
    	{
    		if (fast->next == NULL)
    		{
    			//快指针 到底链表尾结点说明 没有环，此时slow 指向中间结点
    			return 0;
    		}
    		else
    		{
    			if (fast->next != NULL && fast->next->next != NULL)
    			{
    				fast = fast->next->next;
    				slow = slow->next;
    			}
    			else
    			{
    				fast = fast->next;
    			}
    		}
    		//某个时刻 快慢指针相遇，说明此处存在环！
    		if (slow == fast)
    		{
    			return (slow - list) / sizeof(Node);
    		}
    
    	}
    	return 0;
    }
    /*
    去掉单链表中的环，将尾结点的next域置位空。
    环位置结点之后的结点，判断其next域是否为环结点，如果是环节点，说明是尾结点
    */
    Status ClearLoopLinkList(LinkList list)
    {
    	int loopLoc = IsLoopLinkList(list);//环结点位置
    	Node* node = list;
    	Node* loop = NULL;
    	if (loopLoc)
    	{
    		int num = 0;
    
    		while (node->next != NULL)
    		{
    			node = node->next;
    			num++;
    			if (num == loopLoc)
    			{
    				loop = node;
    			}
    			if (num > loopLoc && node->next == loop)
    			{
    				//找到尾结点，尾结点指针域置位空
    				node->next = NULL;
    				break;
    			}
    		}
    	}
    	return OK;
    }

### main.c ###

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include "LinkList.h"
    
    /*
    单链表中尾结点的next指针为空代表着单链表结束了。
    单链表中有环，就是尾结点的next域并为为空，指向了单链表中其他的结点从而形成了环。
    */
    int main(int argc, char *argv[])
    {
    	LinkList list = NULL;
    	CreatLinkListInTail(&list, 6);
    	printf("单链表元素个数:%d\n", LengthLinkList(list));
    	//正常链表的展示
    	printf("正常单链表:\n");
    	PrintLinkList(list);
    	//printf("带环的单链表展示：\n");
    	SetLoopLinkList(list, 3);
    	int loc = IsLoopLinkList(list);
    	printf("环的位置:%d\n", loc);
    	ClearLoopLinkList(list);
    	printf("清除带环单链表的环\n");
    	PrintLinkList(list);
    
    	
    	return 0;
    }

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/78985867
[SouthEast]: /images/20220602/1efb3c18f3f747ffa47dfc3a30b88498.png
[SouthEast 1]: /images/20220602/d611cbf0c1344a47bbbacd16152103c6.png
[SouthEast 2]: /images/20220602/8cd5d7a0a8ea4c55873d85be6a74affb.png