给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
1.正常思路 剑指offer课本讲的很清楚
1)先由快慢指针得道环里的一个节点 //此函数也可以判断是否含有环
2)由环里的节点推断出节点的个数
3)由快慢指针得到环的入口;让快指针先走k个几点(k是环内节点个数)
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (pHead==NULL)
return nullptr;
ListNode * meetingNode = MeetingNode(pHead);//返回的是环内的一个节点
if (meetingNode==NULL)//得到的结果是NULL
return nullptr;
int loopnum=1;
ListNode* PNode1=meetingNode;
while(PNode1->next!=meetingNode)
{
loopnum++;
PNode1=PNode1->next;
}
////已经找到循环内部的个数
///让p2先走k步
PNode1=pHead;
ListNode* PNode2=pHead;
while(loopnum)
{
PNode1=PNode1->next;
loopnum--;
}
//开始走。遇到时候那个点即是环口入点
while(PNode1!=PNode2)
{
PNode1=PNode1->next;
PNode2=PNode2->next;
}
return PNode2;
}
public:
ListNode* MeetingNode(ListNode* pHead)
{
if (pHead==NULL)
return nullptr;
ListNode* slow=pHead->next;
if(slow==NULL)//不是尾部后
return nullptr;
ListNode* fast=slow->next;
while(fast!=NULL&&pHead!=NULL)
{
if (fast==slow)//退出口
return fast;
fast=fast->next;
slow=slow->next;
if(fast!=NULL)//判断尾部节点后有没环
fast=fast->next;
}
return nullptr;
}
};
2。断链 改变链表结构 虽然简单不推荐使用
/*
时间复杂度为O(n),两个指针,一个在前面,另一个紧邻着这个指针,在后面。
两个指针同时向前移动,每移动一次,前面的指针的next指向NULL。
也就是说:访问过的节点都断开,最后到达的那个节点一定是尾节点的下一个,
也就是循环的第一个。
这时候已经是第二次访问循环的第一节点了,第一次访问的时候我们已经让它指向了NULL,
所以到这结束。
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (!pHead->next)
return NULL;
ListNode* previous = pHead;
ListNode* front = pHead ->next;
while (front)
{
previous->next = NULL;
previous = front;
front = front->next;
}
return previous;
}
};