【剑指offer】面试题23：链表中环的入口节点

清疚 2022-03-30 14:08 151阅读 0赞

> **题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。**

解决这个问题的第一步是：**如何确定一个链表中包含环**。可以受前面22题的启发，我们可以用两个指针来解决这个问题。和前面的问题一样，定义两个指针，同时从链表的头节点出发，第一个指针一次走一步，第二个指针一次走两步。如果走得快得指针追上了走得慢的指针，那么链表就包含环；如果走得快得指针走到了链表得末尾都没有追上第一个指针，那么链表就不包含环。

第二步是：**如何找到环的入口**。我们还是可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头节点。如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着走了一圈，又回到了入口节点，交汇处便是环的入口节点。

下面看一个案例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

1、指针P1和P2在初始化时都指向链表的头节点；

2、由于环中有4个节点，所以指针P1先在链表上向前移动4步；

3、指针P1和指针P2以相同的速度在链表上向前移动，直到它们相遇。它们相遇的节点就是环的入口节点。

*  **代码实现**

public class EntryNodeOfLoop {
    
    	class ListNode{
    		private int val;
    		private ListNode next = null;
    		
    		public ListNode(int val){
    			this.val = val;
    		}
    	}
    	
    	// 找到两个指针（一快一慢）相遇处的节点，相遇的节点一定是在环中的
    	public ListNode mettingNode(ListNode head){
    		if(head == null){
    			return null;
    		}
    		
    		ListNode slow = head.next;
    		if(slow == null){
    			// 只有头节点一个节点
    			return null;
    		}
    		
    		ListNode fast = slow.next;
    		while(slow != null && fast != null){
    			if(slow == fast){
    				return fast;
    			}
    			
    			slow = slow.next;      // slow走一步
    			fast = fast.next;  
    			
    			if(fast != slow){
    				fast = fast.next;   // fast走两步
    			}
    		}
    		return null;
    	}
    	
    	// 找到环的入口节点
    	public ListNode entryNodeOfLoop(ListNode head){
    		ListNode mettingNode = mettingNode(head);
    		if(mettingNode == null){
    			return null;
    		}
    		
    		// 得到环中的节点个数
    		int nodesInLoop = 1;
    		ListNode p1 = mettingNode;
    		while(p1.next != mettingNode){
    			p1 = p1.next;
    			++nodesInLoop;
    		}
    		
    		// 移动p1
    		p1 = head;
    		for(int i = 0; i < nodesInLoop; i++){
    			p1 = p1.next;
    		}
    		
    		// 移动p1、p2
    		ListNode p2 = head;
    		while(p1 != p2){
    			p1 = p1.next;
    			p2 = p2.next;
    		}
    		// p1和p2相遇时的节点即是环的入口节点
    		return p1;
    	}
    }

上诉代码的实现主要分为两大部分：即判断是否存在环，然后再找到环的入口节点。虽然代码较长，但是整体思路还是比较清晰的，笨方法也有笨方法的好处，简单易懂。

下面选取几个牛客网中比较简洁的答案：

[https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4][https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4]

*  ### 方法二： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程）

当快慢指针相遇的时候：

此时慢指针走的路程为Sslow = x + m \* c + a

快指针走的路程为：Sfast = x + n \* c + a

又因为：2 Sslow = Sfast

故可得：2 \* ( x + m\*c + a ) = (x + n \*c + a)

从而可以推导出：  
x = (n - 2 \* m )\*c - a  
= (n - 2 \*m -1 )\*c + c - a

即环前面的路程 = 数个环的长度（为可能为0） + c - a。什么是c - a？这是相遇点后，环后面部分的路程（橙色路程）。所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x）从相遇点开始走的那个指针也一定刚好到达环入口点。所以2者会相遇，且恰好相遇在环的入口点。

最后，判断是否有环，且找环的算法复杂度为：时间复杂度：O(n)、空间复杂度：O(1)。

public class EntryNodeOfLoop_Method2 {
    
    	class ListNode{
    		private int val;
    		private ListNode next = null;
    		
    		public ListNode(int val){
    			this.val = val;
    		}
    	}
    	
    	public ListNode entryNodeOfLoop(ListNode head){
    		if(head == null || head.next == null || head.next.next == null){
    			return null;
    		}
    		
    		ListNode fast = head.next.next;   // 走两步
    		ListNode slow = head.next;        // 走一步
    		
    		// 先判断有没有环
    		while(fast != slow){
    			if(fast.next != null && fast.next.next != null){
    				fast = fast.next.next;
    				slow = slow.next;
    			}else{
    				// 没有环
    				return null;
    			}
    		}
    		
    		// 循环出来的话就是有环，此时 fast == slow
    		fast = head;
    		while(fast != slow){
    			fast = fast.next;
    			slow = slow.next;
    		}
    		return slow;
    	}
    }

这种方法要比第一种方法简单的多，但是不容易想到，特别是在判断有环后找入口节点时的操作很简单。

*  ### 方法三： ###
 *  第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
 *  第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。

public class EntryNodeOfLoop_Method3 {
    
    	class ListNode{
    		private int val;
    		private ListNode next = null;
    		
    		public ListNode(int val){
    			this.val = val;
    		}
    	}
    	
    	public ListNode entryNodeOfInLoop(ListNode head){
    		if(head == null || head.next == null){
    			return null;
    		}
    		
    		ListNode p1 = head;
    		ListNode p2 = head;
    		
    		while(p2 != null && p2.next != null){
    			p1 = p1.next;
    			p2 = p2.next.next;
    			if(p1 == p2){
    				// p1和p2相遇，证明有环
    				p2 = head;
    				while(p1 != p2){
    					p1 = p1.next;
    					p2 = p2.next;
    				}
    				if(p1 == p2){
    					return p1;
    				}
    			}
    		}
    		return null;
    	}
    }

第3种方法和第2种方法思路是一样的，只是代码实现上略有差别。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220330/688b971fbe1f417bbac63fe475eb463c.png
[https_www.nowcoder.com_questionTerminal_253d2c59ec3e4bc68da16833f79a38e4]: https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220330/9682cff1ccd44c34bd85ca427f0d5048.png