题目描述
- 如果一个链表中包含环，如何找出环的入口节点
-
举例说明，下图这个链表中环的入口节点是节点3
image.png
题目解读
- 确定一个链表中是否包含环
- 得到环中节点的数目
- 找到环的入口
前期准备
- 定义一个节点
struct ListNode{
int val;
struct ListNode *next;
ListNode(int x):
val(x),next(NULL){
}
};
- 尾插法创建链表，这个链表和一般的创建链表的方式有点不同。因为这个链表是存在环的，要确定环的位置。
ListNode* create()
{
ListNode *p,*head,*tail,*loop;
head = tail = NULL;
for(int i = 1;i<7;i++)
{
p = new ListNode(i);
if(i == 3)
{
loop = p;
}
if(!head)
{
head = p;
}
else
{
tail->next = p;
}
tail = p;
}
tail->next = loop;//连成环
return head;
}
- 输出函数
void print_Node(ListNode *head)
{
for(int i =1;i<7;i++)
{
cout<<head->val<<" ";
head = head->next;
}
cout<<endl;
}
核心代码
- 第一步:找到环中的节点，定义一个find_loop_sum()的函数，传入参数为头结点。
1，定义两个指针比如快指针和慢指针。为了增强鲁棒性，检查头结点的下一个节点不为空时，把头结点的下一个节点赋值为慢节点。头结点的下下一个节点赋值为快节点。
2，判断是否存在环。循环遍历快慢节点，直到快节点追上慢节点以此说明该链表中存在环。
3，计算环中存在几个节点。慢节点不动，让快结点遍历使其再次遇到慢节点，记录期间经过几个节点。这个节点数加一就是环中的节点数。
具体代码如下:
int find_loop_sum(ListNode* pHead)
{
int n =0;
ListNode *kuai = NULL;//定义快指针
ListNode *man = NULL;//定义慢指针
if(pHead->next)
{ //若头结点的下一个节点不为空
man = pHead->next;//则慢节点就是头结点的下一个节点
}
else //若头结点的下一个节点为空，则返回0
{
return 0;
}
if(man->next)
{ // 若慢节点的下一个节点不为空
kuai = man->next; //定义快结点为慢节点的下一个节点
}
else //若慢节点的下一个节点为空，则返回0
{
return 0;
}
while(kuai !=man)
{ //while()循环 条件是若快结点不等于慢节点 说明该链表不存在环
if(kuai->next && kuai->next->next)
{//若快节点的下一个节点和下下一个节点存在
kuai = kuai->next->next; //快节点一次走两步
man = man->next; //慢节点一次走一步
}
else
{ //直到快节点追上慢节点，证明该链表存在环，循环结束
return 0;
}
}
while(kuai->next !=man)
{ //计算环中有几个节点
kuai = kuai->next;
n++;
}
n++;
cout<<"环中节点的个数"<<n<<endl;
return n;
}
- 第二步:找环的入口节点。定义一个函数名为EntryNodeOfLoop()。
1，从上一个函数中得到环中节点个数，接下来的过程就类似于面试题22。
2，定义两个指针p1和p2。先让p1节点往前走n-1步，然后p2从头开始移动，此时p1和p2一起遍历直到p1节点等于p2节点时说明找到入口节点了。
//找环入口节点的函数
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(!pHead)
{//若头结点为空
return NULL;
}
int n = find_loop_sum(pHead); //得到环中节点个数
if(n == 0)
{
return NULL;
}
ListNode *p1 = pHead;
ListNode *p2 = pHead;
for(int i =0;i<n;i++)
{ //p1节点往前先走n步
p1 = p1->next;
}
while(p1 != p2)
{ //while()循环，只要p1节点不等于p2节点，就一直移动直到p1节点等于p2节点即入口节点
p1 = p1->next; //p1从第n个节点往后移动
p2 = p2->next; //p2从头结点开始往后移动
}
return p1;
}
补充主函数
int main(){
Solution ss;
ListNode *head,*loop;
head = loop =NULL;
head = ss.create();//创建链表
ss.print_Node(head);//输出链表
loop = ss.EntryNodeOfLoop(head);//进入函数
cout<<"环的入口结点的数据:"<<loop->val<<endl;//输出环的入口结点
}
这道题涉及到环，确实比较能开阔思路。目前还处于能看懂代码，等到自己能写出来估计还有一段时间的练习，不过这样把看懂的过程记录下来没事拿来看看也是一个学习的过程。
参考
