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

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

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 题目描述 ##

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

链表结点定义如下：

struct ListNode \{  
    int val;  
    struct ListNode \*next;  
    ListNode(int x) :  
        val(x), next(NULL) \{  
    \}  
\};

思路：（剑指offer第二版 P139）

> `两个指针一个fast、一个slow同时从一个链表的头部出发，`
> 
> `fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇，`
> 
> `此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），`
> 
> `这次两个指针一次走一步，相遇的地方就是入口节点。`

C++实现代码如下：

ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
    	ListNode* fast = pHead;
    	ListNode* slow = pHead;
    	//1、若有环，fast一次走一步，slow一次走两步，找到两个指针相遇的结点
    	while(fast != NULL && fast->next != NULL)
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if(fast == slow)
    			break;
    	}
    	//2、说明无环，直接返回NULL
    	if(fast == NULL || fast->next == NULL)
    		return NULL;
    	//3、从相遇结点开始，让fast重新指向头结点，然后两个指针同步往后移动，再次相遇的结点即为环的入口结点
    	fast = pHead;
    	while(fast != slow)
    	{
    		fast = fast->next;
    		slow = slow->next;
    	}
    	return fast;
    }

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538

发表评论取消回复

表情：

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

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

相关阅读

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

文章目录一、题目解析二、代码三、总结一、题目解析给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出

骑猪看日落/ 2022年12月06日 15:21/ 0 赞/ 166 阅读

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

[NowCoder][] 题目描述一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。解题思路使用双指针，一个指针 fast 每次移动两

妖狐艹你老母/ 2022年11月25日 13:08/ 0 赞/ 132 阅读

相关剑指offer（C++）——链表中环的入口结点

题目描述一个链表中包含环，请找出该链表的环的入口结点 struct ListNode { int val; struct Lis

小鱼儿/ 2022年06月16日 21:15/ 0 赞/ 174 阅读

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

题目描述一个链表中包含环，请找出该链表的环的入口结点。实验平台：[牛客网][Link 1] -------------------- 解决思路： ![这里

绝地灬酷狼/ 2022年05月26日 00:53/ 0 赞/ 182 阅读

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

题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。时间限制：1秒；空间限制：32768K；本题知识点：链表解题思路思路

迈不过友情╰/ 2022年04月21日 23:36/ 0 赞/ 204 阅读

相关剑指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 赞/ 219 阅读

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

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

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

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

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

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