环形链表II

拼搏现实的明天。 2022-01-17 03:47 204阅读 0赞

## 1、题目描述 ##

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
    输出：tail connects to node index 1
    解释：链表中有一个环，其尾部连接到第二个节点。

![在这里插入图片描述][20190612185944367.png]  
示例 2：

输入：head = [1,2], pos = 0
    输出：tail connects to node index 0
    解释：链表中有一个环，其尾部连接到第一个节点。

![在这里插入图片描述][20190612190006245.png]  
示例 3：

输入：head = [1], pos = -1
    输出：no cycle
    解释：链表中没有环。

![在这里插入图片描述][20190612190023945.png]

## 2、解法 ##

## 2.1 Floyd 算法 ##

想法

当然一个跑得快的人和一个跑得慢的人在一个圆形的赛道上赛跑，会发生什么？在某一个时刻，跑得快的人一定会从后面赶上跑得慢的人。

算法

Floyd 的算法被划分成两个不同的 阶段 。在第一阶段，找出列表中是否有环，如果没有环，可以直接返回 null 并退出。否则，用 相遇节点 来找到环的入口。

阶段 1

这里我们初始化两个指针 - 快指针和慢指针。我们每次移动慢指针一步、快指针两步，直到快指针无法继续往前移动。如果在某次移动后，快慢指针指向了同一个节点，我们就返回它。否则，我们继续，直到 while 循环终止且没有返回任何节点，这种情况说明没有成环，我们返回 null 。

下图说明了这个算法的工作方式：  
![在这里插入图片描述][2019061219032242.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]  
阶段 2

给定阶段 1 找到的相遇点，阶段 2 将找到环的入口。首先我们初始化额外的两个指针： ptr1 ，指向链表的头， ptr2 指向相遇点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点。

下面的图将更好的帮助理解和证明这个方法的正确性。  
![在这里插入图片描述][20190612190348717.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]  
我们利用已知的条件：慢指针移动 1 步，快指针移动 2 步，来说明它们相遇在环的入口处。（下面证明中的 tortoise 表示慢指针，hare 表示快指针）

![在这里插入图片描述][20190612190517457.png]

因为 F=b，指针从 h 点出发和从链表的头出发，最后会遍历相同数目的节点后在环的入口处相遇。

代码实现如下：

public ListNode detectCycle(ListNode head) { 
    	if(head == null || head.next==null) { 
    		return null;
    	}
    	ListNode slow = head.next, fast = head.next.next;
    	while(fast != null) { 
    		if(fast.next == null) { 
    			return null;
    		}
    		if(slow == fast) { 
    			//快慢指针相遇了
    			break;
    		}
    		slow = slow.next;
    		fast = fast.next.next;
    		
    	}
    	//无环
    	if(fast == null) { 
    		return null;
    	}
    	
    	//有环
    	ListNode start = head;
    	while(start != slow) { 
    		start = start.next;
    		slow = slow.next;
    	}
    	return slow;
       }

[20190612185944367.png]: /images/20220117/87625fe7b2be4452b7e237b8fa291b4b.png
[20190612190006245.png]: /images/20220117/9e01a64f1d684a88b8410d81900e7cbb.png
[20190612190023945.png]: /images/20220117/22cd329682c04c559d42cdf8b5bbf834.png
[2019061219032242.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220117/5a9752b315b94e3580d4a1cd5689a64b.png
[20190612190348717.png_x-oss-type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220117/f5e186a461d94e94a8406663312848c8.png
[20190612190517457.png]: /images/20220117/0a23121b15e5487f92f1c65fc5868fcb.png