判断一条链表中有无环路

桃扇骨 2023-01-21 02:25 15阅读 0赞

### 两种链表 ###

一、普通单链表  
![在这里插入图片描述][20210514092346455.png_pic_center]

二、有环链表  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]

### 问题：判断一条链表中是否存在环。 ###

*  **思路一**：哈希存储，通过set集合存储遍历过的结点，遍历过程中检查set，若set中已存在某节点，则证明有环，返回true，若遍历正常结束，最终返回false，无环。（该方法易实现，此处略写。）
 *  **思路二**：双指针、快慢指针，设置一个fast指针和slow指针，slow每次移动一次（`slow = slow.next`），fast 每次移动两次（`fast = fast.next.next`)。若存在环，fast指针先进入环内循环，slow后进入，在环中slow与fast相遇，则证明环存在，返回true；若无环，fast一次遍历结束，返回false。

#### 方法二动图演示 ####

![在这里插入图片描述][20210514092548748.gif_pic_center]

#### 方法二代码实现 ####

链表结构体

typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link;

int judgeRing(Link head){
        
    	if(head == NULL || head->next == NULL){
        
    		return -1;
    	}
        // 设快慢指针指向第一结点。
    	Link slow = head->next,fast = head->next;
        // fast如果正常遍历结束，说明没有环存在。
    	while(fast!=NULL  && fast->next!=NULL){
        
            // 慢指针每次移动一次，快指针移动两次
    		slow = slow->next;
    		fast = fast->next->next;
            // 快慢指针再次相遇时，证明环存在。
    		if(slow == fast){
        
    			return 1;
    		}
    	}
    	return 0; 
    }

[20210514092346455.png_pic_center]: /images/20221021/b62154b78e7146628904e2da4a9fbf02.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xfamRfZ3VsdWx1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/d5804a35dab644fb9d8b6c03cb927501.png
[20210514092548748.gif_pic_center]: /images/20221021/0171e3dadebd46118488bed7e7c5cb0d.png