链表中环的入口结点

た入场券 2021-11-09 08:40 282阅读 0赞

## 题目描述 ##

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

/**
     * 
     * @author gentleKay
     * 题目描述
     * 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
     */
    
    public class Main54 {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		
    	}
    	
    	 public class ListNode {
    	    int val;
    	    ListNode next = null;
    
    	    ListNode(int val) {
    	        this.val = val;
    	    }
    	}
    	 
    	 
    	public ListNode EntryNodeOfLoop(ListNode pHead){
            if (pHead == null || pHead.next == null) {
            	return null;
            }
            
            ListNode p1 = pHead;
            ListNode p2 = pHead;
            while (p2 != null && p2.next != null) {
            	p1 = p1.next; // 一个慢指针
            	p2 = p2.next.next; // 一个快指针   这样如果存在环的话一定会相遇 p1 == p2;
            	if (p1 == p2) {
            		p2 = pHead;  // 在设置一个指针，为慢指针。
            		while (p1 != p2) {
            			p1 = p1.next;
            			p2 = p2.next;
            		}
            		if (p1 == p2) { //一旦他们相等 就返回 这个结点
            			return p1;
            		}
            	}
            }
            return null;
        }
    
    }

转载于:https://www.cnblogs.com/strive-19970713/p/11200067.html

发表评论取消回复

表情：

评论列表（有 0 条评论，282人围观）

还没有评论，来说两句吧...

相关阅读

相关 BM7 链表中环的入口结点

描述给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。数据范围： n\\le10000n≤10000，1<=结点值<=100001<

灰太狼/ 2023年10月04日 17:37/ 0 赞/ 43 阅读

相关链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。先找到环的节点数：一块一慢两个指针，快的追上慢的指针时，该指针指向的结点在环内，遍历一次环拿到节点

╰+哭是因爲堅強的太久メ/ 2023年02月20日 12:17/ 0 赞/ 7 阅读

相关链表中环的入口结点

![这里写图片描述][70] 一、分析判断链表有环的算法中出现过的策略，分别按1x和2x速度遍历，总会相遇。假设环长为n。容易知道，当1x的指针p1和2x的指针

今天药忘吃喽~/ 2022年05月24日 05:06/ 0 赞/ 181 阅读

相关编程题：链表中环的入口结点

题目描述一个链表中包含环，请找出该链表的环的入口结点。思路：假设x为环前面的路程，a为环入口到相遇点的路程， c为环的长度

╰+攻爆jí腚メ/ 2022年05月21日 09:45/ 0 赞/ 154 阅读

相关剑指offer:链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 AC C++ Solution: 解题思路：还是使用两个指针，一个fast，

小鱼儿/ 2022年04月10日 09:23/ 0 赞/ 206 阅读

相关【剑指Offer】（链表）链表中环的入口结点

题目链接：[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&tqId=11

深藏阁楼爱情的钟/ 2022年03月17日 14:24/ 0 赞/ 232 阅读

相关剑指Offer-链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。解题思路—HashMap：使用HashMap存储链表结点，当链表结点重复时，即有环

曾经终败给现在/ 2022年02月14日 03:22/ 0 赞/ 218 阅读

相关链表中环的入口结点

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 / @author gentleKay

た入场券/ 2021年11月09日 08:40/ 0 赞/ 283 阅读

相关剑指offer 链表中环的入口结点

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。链表结点定义

待我称王封你为后i/ 2021年11月05日 23:56/ 0 赞/ 286 阅读

相关剑指offer：链表中环的入口结点

试题：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。代码： / public class ListNode {

Myth丶恋晨/ 2021年06月24日 16:10/ 0 赞/ 397 阅读