判断单向链表是否有环

红太狼 2022-02-20 08:12 287阅读 0赞

### 判断单链表是否有环 ###

*  问题汇总
 *   *  判断是否有环
     *   *  思路
         *  代码
     *  找出环的入口点
     *   *  思路
         *  代码
     *  求环的长度
     *   *  思路
         *  代码
     *  求环上距离任意一点最远的点
     *  判断两个无环链表是否相交
     *  判断相交的位置

# 问题汇总 #

1.  给一个单链表，判断其中是否有环的存在；
2.  如果存在环，找出环的入口点；
3.  如果存在环，求出环上节点的个数；
4.  如果存在环，求出链表的长度；
5.  如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.  如何判断两个无环链表是否相交；
7.  如果相交，求出第一个相交的节点；

## 判断是否有环 ##

### 思路 ###

创建两个指针 fast 和 slow 指向头结点, 无限循环, 每次循环 fast 走两步, slow 走一步. 如果 fast 碰到 NULL 说明没有环, 如果 fast 碰到 slow 说明有环.

### 代码 ###

int checkLoop(Node* head) { 
    	Node* fast = head;
    	Node* slow = head;
    	while (1) { 
    		fast = fast->next;
    		if (fast == NULL) return 0;
    		fast = fast->next;
    		if (fast == NULL) return 0;
    		slow = slow->next; 
    		if (fast == slow) return 1;
    	}
    }

## 找出环的入口点 ##

### 思路 ###

这是个数学题, 首先要明白:  
**如果 fast 遇到了 slow, 说明 fast 比 slow 多走了整整 n 圈 ( n >= 1 )**  
这个理解了之后, 进行数学解答:

设 slow 走了  s s s 步, 则 fast 走了  2 s 2s 2s 步

设圈的长度为 L L L

因为 fast 比 slow 多走了整整 n 圈, 所以

2 s − s = s = n × L 2s - s = s = n \\times L 2s−s=s=n×L

又因为 slow 是从头结点走到环的入口, 又从环的入口走到了重合点  
设环的入口到头结点的长度为  A A A, 二者的重合点到圈的入口为  X X X  
所以

s = A + X s = A + X s=A\+X

所以

X + A = n × L X + A = n \\times L X\+A=n×L

**!!! 以下结论很关键 !!!**

**当一个指针位于环中, 到环的起点的距离是  x x x 时, 若指针向前移动了  y y y 步, 那么它的最终位置到环的起点的距离是  ( x + y ) % L (x+y) \\% L (x\+y)%L**

所以

当一个指针位于重合点时, 如果它向前走  A A A 步, 那么它的最终位置就是环的起点, 即

( X + A ) % L = ( n × L ) % L = 0 (X + A) \\% L = (n \\times L) \\% L = 0 (X\+A)%L=(n×L)%L=0

同时, 若一个指针从头结点向前走  A A A 步, 那么它的最终位置**也**是环的起点 (因为环的起点到头结点的距离是  A A A)

**所以, 如果两个指针分别从头结点和重合点同时向前走, 每次都只走一步, 那么它们会和的地方就是环的起点**

### 代码 ###

// 检查是否有环, 如果有环找出重合点
    Node* checkLoop(Node* head) { 
    	Node* fast = head;
    	Node* slow = head;
    	while (1) { 
    		fast = fast->next;
    		if (fast == NULL) return NULL;
    		fast = fast->next;
    		if (fast == NULL) return NULL;
    		slow = slow->next; 
    		if (fast == slow) return fast;
    	}
    }
    // 计算环入口距离链表头结点的距离
    int getPreloop(Node* head) { 
    	Node* p1 = checkLoop(head);
    	Node* p2 = head;
    	int count = 0;
    	while (p1 != p2) { 
    		p1 = p1->next;
    		p2 = p2->next;
    		count++;
    	}
    	// 此时 p1 就是入口点
    	return count;
    }

## 求环的长度 ##

### 思路 ###

如果 fast 和 slow 重合, 说明 slow 已经位于环中, 那么令一个新的指针从重合点的位置一步一步向前走, 最终一定会再和 slow 重合, 而走的步数就是环的长度.

### 代码 ###

// 检查是否有环, 如果有环找出重合点
    Node* checkLoop(Node* head) { 
    	Node* fast = head;
    	Node* slow = head;
    	while (1) { 
    		fast = fast->next;
    		if (fast == NULL) return NULL;
    		fast = fast->next;
    		if (fast == NULL) return NULL;
    		slow = slow->next; 
    		if (fast == slow) return fast;
    	}
    }
    // 计算环的长度
    int getLoopLen(Node* head) { 
    	Node* p1 = checkLoop(head);
    	Node* p2 = p1;
    	int count = 1;
    	p2 = p2->next;
    	while (p1 != p2) { 
    		p2 = p2->next;
    		count++;
    	}
    	return count;
    }

## 求环上距离任意一点最远的点 ##

显然, 最远距离是  f l o o r ( L 2 ) floor(\\frac\{L\}\{2\}) floor(2L)

## 判断两个无环链表是否相交 ##

两个指针分别找到两个链表最后一个节点, 检查最后一个节点是否是一样的即可.

## 判断相交的位置 ##

标准答案是, 将一个链表的尾巴连接到另一个链表的头部, 从而组成一个带环的链表, 然后就可以把这个问题转化为寻找环的入口. 这方法真巧…

如果我们不允许修改链表, 我的想法是:

维护两个和链表等长的数组, 记录两个指针分别走过的所有节点  
然后倒序遍历两个数组, 直到找到两个不一样的值, 那么该值的上一个值便是相交点.