【题23 链表中环的入口节点】

冷不防 2022-03-25 03:14 173阅读 0赞

**【题23 链表中环的入口节点】**  
**【题目】**  
如果一个链表中包含环，如何找出环的入口节点？  
**例如：**  
如图的链表中，环的入口节点是节点3

**分析：**

1.  如何确定一个链表中包含环？  
    用两个指针，同时从头节点出发，一个指针一次走一步，另一个指针一次走两步，  
    如果走到快的指针追上了走得慢的指针，那么链表包含环  
    如果走得快的指针到了链表末尾，都没有追上第一个指针，那么链表就不包含环
2.  如何找到环的入口？  
    两个指针P1，P2，指向头节点，如果链表中的环有n个节点，则指针P1先在链表上向前移动n步，然后两个指针以相同的速度向前移动。当第二个指针指向环的入口节点时，第一个指针已经围绕着环走了一圈，又回到了入口节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]
3.  如何得到环中节点数目  
    用一快一慢2个指针，如果指针相遇，则表明链表中存在环，2个指针相遇的节点一定是在环中，可以从这个节点出发，一边继续向前移动，一边计数，当再次回到这个节点时，就可以得到环中节点数了。

**实现**

package ti23;
    
    class ListNode{
    	int value;
    	ListNode next;
    }
    public class Lianxi {
    	public static void main(String[] args) {
    		Lianxi test = new Lianxi();
    		
    		ListNode head = new ListNode();
    		ListNode temp1 = new ListNode();
    		ListNode temp2 = new ListNode();
    		ListNode temp3 = new ListNode();
    		ListNode temp4 = new ListNode();
    		ListNode temp5 = new ListNode();
    		
    		head.value = 1;
    		temp1.value = 2;
    		temp2.value = 3;
    		temp3.value = 4;
    		temp4.value = 5;
    		temp5.value = 6;
    		
    		head.next = temp1;
    		temp1.next = temp2;
    		temp2.next = temp3;
    		temp3.next = temp4;
    		temp4.next = temp5;
    		temp5.next = temp3;
    		
    		ListNode resultNode = test.getEnterNode(head);
    		if(resultNode != null){
    			System.out.println(resultNode.value);
    		}else{
    			System.out.println("您输入的参数有误");
    		}
    	}
    	
    	public ListNode getEnterNode(ListNode head){
    		//参数校验
    		if(head == null){
    			return null;
    		}
    		
    		//如果有环，第一个和第二个指针在环中相遇时的节点
    		ListNode meetingNode = meetingNode(head);
    		
    		int ringLength = 0; //环的长度
    		if(meetingNode != null){//如果存在环，就求出环的长度
    			ListNode tempNode= meetingNode;
    			meetingNode = meetingNode.next;
    			while(meetingNode != tempNode){
    				ringLength++;
    				meetingNode = meetingNode.next;
    			}
    			ringLength++;
    		}else{
    			return null;//如果不存在环，就返回null
    		}
    		
    		ListNode ahead = head;//第一个指针
    		ListNode behind = head;//第二个指针
    		
    		while(ringLength > 0){
    			ahead = ahead.next;//第一个指针现在链表上向前移动ringLength步
    			ringLength--;
    		}
    		while(ahead != behind){
    			ahead = ahead.next;
    			behind = behind.next;
    		}
    		return behind;
    	}
    	//在链表存在环的情况下，找到一块一慢两个指针相遇的节点
    	public ListNode meetingNode(ListNode head){
    		//参数校验
    		if(head == null){
    			return null;
    		}
    		ListNode behind = head.next;//后面的指针
    		
    		//如果只有一个节点直接返回null
    		if(behind == null){
    			return null;
    		}
    		ListNode ahead = behind.next;//前面的指针
    		while(behind != null && ahead != null){
    			if(behind == ahead){
    				return ahead;
    			}
    			//behind指针在链表上移动一步
    			behind = behind.next;
    			//ahead指针在链表上移动两步
    			ahead = ahead.next;
    			if(head != null){
    				ahead = ahead.next;
    			}
    		}
    		return null;
    	}
    }

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80167240][https_blog.csdn.net_weixin_37672169_article_details_80167240]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220325/ef9ebaa5614646e6b3b3901ec9be2a9c.png
[https_blog.csdn.net_weixin_37672169_article_details_80167240]: https://blog.csdn.net/weixin_37672169/article/details/80167240