链表中环的入口结点
2020-07-02 本文已影响0人
UAV
题目描述
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
思路
- 判断链表中是否存在环。
- 判断环中结点个数。
- 计算链表中环的入口结点。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
//1.定义两个指针,一个指针一次走一步,一个指针一次走两步,后判断链表是否有环。
ListNode*meetingNode = MeetingNode(pHead);
if (meetingNode == NULL) {
return NULL;
}
//2.有环,确定环的数量
int nodeslnLoop = 1;
//当前结点已经在环上了所以 nodeslnloop=1
ListNode *pNode1 = meetingNode;
//直接用结点比较
while (pNode1->next!= meetingNode)
{
pNode1 = pNode1->next;
nodeslnLoop++;
}
//3.确定环的入口结点
//先移动pNode1,次数为环中结点数目
pNode1 = pHead;
for (int i = 0; i <nodeslnLoop; i++)
{
pNode1 = pNode1->next;
}
//再同时移动pNode1和pNode2
ListNode *pNode2 = pHead;
while (pNode1!=pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
ListNode* MeetingNode(ListNode *pHead) {
if (pHead == NULL) {
return NULL;
}
//慢指针一次走一步
ListNode *pSlow = pHead->next;
if (pSlow == NULL) {
return NULL;
}
//快指针走两步
ListNode *pFast = pSlow->next;
while (pFast!= NULL&&pSlow!= NULL)
{
//指针相遇
if (pFast == pSlow) {
return pFast;
}
//慢指针走一步
pSlow = pSlow->next;
//快指针走两步
pFast = pFast->next;
if (pFast != NULL) {
pFast = pFast->next;
}
}
return NULL;
}
};