面试题23:链表中环的入口节点

题目描述

  • 如果一个链表中包含环,如何找出环的入口节点
  • 举例说明,下图这个链表中环的入口节点是节点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;//输出环的入口结点
 }

这道题涉及到环,确实比较能开阔思路。目前还处于能看懂代码,等到自己能写出来估计还有一段时间的练习,不过这样把看懂的过程记录下来没事拿来看看也是一个学习的过程。
参考

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容