判断一个链表是否有环

骑猪看日落 2022-04-04 14:27 247阅读 0赞

### 判断一个链表是否有环 ###

*  方法一
 *  方法二
 *  方法三

给出一个单向链表，判断链表中是否存在环。虽然是一个实际工作中基本不会碰到的场景，但是面试的时候总是会考到，因此整理下各种解法，以免需要的时候用到。温故而知新！

# 方法一 #

第一种方法是很容易想到，利用空间来换时间：遍历链表中的每一个节点，放入一个容器中（此处使用std::set，查找速度快），每次插入容器的时候，判断是否已经存在相同节点元素，如果存在，那么就是有环的。  
代码简单演示如下：

#include <set>
    #include <iostream>
    
    typedef struct Node
    {
    	int nVal;
    	Node *pNext;
    }*LinkNode;
    
    int HasLoop1(LinkNode L)
    {
    	std::set<LinkNode> nodeSet;
    
    	LinkNode pTemp = L;
    	while (pTemp != nullptr)
    	{
    		auto it = nodeSet.insert(pTemp);
    		if (it.second)	//返回的是一个key-value键值对，value为是否插入成功，对于set而言，如果存在，那么就插入失败
    		{
    
    		}
    		else
    		{
    			int nDistance = std::distance(nodeSet.begin(), it.first);
    			std::cout << "第" << nDistance << "个节点是环" << std::endl;
    			return 1;
    		}
    
    		pTemp = pTemp->pNext;
    	}
    	return 0;
    }

下面两种方法就只写函数实现了，节点定义都是一样的。

# 方法二 #

第二种方法：使用p,q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样，步数不等，则存在环。  
     这种方法最差的情况下，时间复杂度可以达到O(n^2)，因此不是很推荐，但也是一种方法，可以拓展下思路。  
     代码简单演示如下：

int HasLoop2(LinkNode L)
      {
        LinkNode cur1 = L;     //定义节点cur1
        int pos1 = 0;   //cur1的步数
        
        //套了两层循环，cur1不动，cur2从头循环到尾
        while(cur1)   //cur1节点存在
        {
            LinkNode cur2 =L;    //定义节点cur2
            int pos2 = 0;   //cur2的步数
            while(cur2 )//cur2节点存在
            {
                if(pos1 = pos2)   //当cur1和cur2到达相同节点时
                {
                    if(pos1 == pos2)    //如果走过的步数一样，说明没有环
                       break;
                    else    
                    {
                        printf("环的位置在第%d个节点处\n",pos2);
                        return 1;   //有环并返回
                    }
                }
                cur2 = cur2->next; //如果没发现环，继续下一个节点
                pos2++;//cur2步数自增
            }
            cur1 = cur1->next; //cur1继续下一个节点
            pos1++;  
        }
        return 0;
      }

# 方法三 #

最后一种方法，也可以说是标答了，我当初在学校时刷的剑指offer，以及在牛客网上的答案，推荐的答案都是一样的：快慢指针。使用p,q两个指针，P每次向前走一步，q每次向前走两步，若在某个时候p = q，则存在环。  
     大家有没有想到，为什么快慢指针中的快指针要走两步呢（慢指针走一步原因都知道，因为要走遍所有节点）。那是因为要成环，至少要有三个节点，如果快指针走三步，那么对于三个节点的环，它永远只能走一个固定点，但是如果走两步，不论从哪一个节点开始，它都可以把环中的三个节点全部遍历完。  
     代码简单演示如下：

int HasLoop3(LinkNode L)
    {
    	LinkNode p;
    	LinkNode q;
    
    	//一层循环 
    	while (p != NULL && q != NULL && q->next != NULL)
    	{
    		p = p->pNext; //慢指针走一步
    		if (q->pNext != NULL)
    			q = q->pNext->pNext;  //快指针走两步
    
    		if (p == q)
    			return 1;
    	}
    	return 0;
    }