链表中环的入口节点

柔光的暖阳◎ 2023-03-02 10:22 14阅读 0赞

**计算链表中环的节点数和环的入口节点**

*利用快慢指针可以解决这个问题（看下面的代码）*

//链表的结构类型
    struct ListNode { 
    	int m_val;
    	ListNode* m_pNext;
    };
    
    
    //找到环中任一节点（快慢节点相遇的节点）
    ListNode* MettingNode(ListNode* pHead)
    { 
    	if (pHead == nullptr)
    	{ 
    		return nullptr;
    	}
    
    	ListNode* pSlow = pHead->m_pNext;
    	if (pSlow == nullptr)
    	{ 
    		return nullptr;
    	}
    
    	ListNode* pFast=pSlow->m_pNext;
    	if (pFast == nullptr)
    	{ 
    		return nullptr;
    	}
    
    	while (pFast != nullptr && pSlow != nullptr)
    	{ 
    		if (pFast == pSlow)
    		{ 
    			return pSlow;
    		}
    		pSlow = pSlow->m_pNext;
    		pFast = pFast->m_pNext;
    
    		if (pFast != nullptr)
    		{ 
    			pFast = pFast->m_pNext;
    		}
    	}
    	return nullptr;
    }
    
    //计算环的节点数，并且找到换的入口
    ListNode* EntryNodeLoop(ListNode* pHead)
    { 
    	ListNode* mettingnode = MettingNode(pHead);
    	if (mettingnode == nullptr)
    	{ 
    		return nullptr;
    	}
    
    	//得到环的节点数
    	int NodeNumber = 0;
    	ListNode* pNode1 = mettingnode;
    	while (pNode1 != mettingnode)
    	{ 
    		pNode1 = pNode1->m_pNext;
    		++NodeNumber;
    	}
    
    	//找环的节点
    	pNode1 = pHead;
    	for (int i = 0; i < NodeNumber; ++i)
    	{ 
    		pNode1 = pNode1->m_pNext;
    	}
    	ListNode* pNode2 = pHead;
    	while (pNode2 != pNode1)
    	{ 
    		pNode1 = pNode1->m_pNext;
    		pNode2 = pNode2->m_pNext;
    	}
    	return pNode1;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关牛客-链表中环的入口节点(Java)

链表中环的入口节点【题目描述】对于一个给定的链表，返回环的入口节点，如果没有环，返回null 【思路】 1. 首先判断有没有环我们可以设置两个指针

待我称王封你为后i/ 2023年10月04日 12:59/ 0 赞/ 64 阅读

相关链表中环的入口节点

计算链表中环的节点数和环的入口节点利用快慢指针可以解决这个问题（看下面的代码） //链表的结构类型 struct ListNode { int

柔光的暖阳◎/ 2023年03月02日 10:22/ 0 赞/ 15 阅读

相关 28：链表中环的入口节点

链表中环的入口节点如果一个链表中包含环，如何找出环的入口节点？ public class Offer29 { public static vo

r囧r小猫/ 2023年03月01日 10:11/ 0 赞/ 1 阅读

相关链表返回环的入口节点

题目描述对于一个给定的链表，返回环的入口节点，如果没有环，返回null 拓展：你能给出不利用额外空间的解法么？说明：本题目包含复杂数据结构ListNode，

矫情吗；*/ 2022年12月21日 04:43/ 0 赞/ 168 阅读

相关链表中环的入口节点

链表中环的入口节点 1、参考资料 https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425a

Dear 丶/ 2022年12月05日 00:56/ 0 赞/ 196 阅读

相关链表中环的入口节点

[https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&rp=1&ru=%2Ft

柔光的暖阳◎/ 2022年11月30日 04:20/ 0 赞/ 202 阅读

相关链表问题_链表中环的入口节点

题目：一个链表中包含环路，求链表的入口节点。分析：根据求[链表中倒数第K个节点][K]的方法，这个问题可以分为两个步骤：1、判断链表中的节点个数记为K，对于这个可以采用一

矫情吗；*/ 2022年05月21日 07:23/ 0 赞/ 247 阅读

相关链表中环的入口节点

问题描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。有环链表类似于下图中的链表： ![70][] 可以看到该链表中有一个环，其中橙

缺乏、安全感/ 2022年05月14日 03:56/ 0 赞/ 221 阅读

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

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

冷不防/ 2022年03月25日 03:14/ 0 赞/ 226 阅读

相关链表之查找环的入口节点

思路：设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一

亦凉/ 2021年09月18日 04:56/ 0 赞/ 662 阅读