【C/C++练习题】找出链表中环的入口节点

《剑指Offer》面试题23：链表中环的入口结点

1 题目

一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中，环的入口结点是结点3。

2 算法思路

1. 找出环中的某一个节点：分别设置指针pSlow pFast在环中遍历元素，pFast的速度快，两个指针最终会在环中的某位置相遇
2. 计算环中节点的个数：从节点出发，一边遍历节点边统计个数，当再次回到起点的时候，得总节点个数k
3. 找出入口节点：设置pFast为pSlow右边第k个指针，同时移动两指针。直到相遇，得入口节点

3 代码

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include "cstdlib"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：找出链表中环的入口节点
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m_nValue;
     
    
   

    

     

    
    

     

      	node* m_pNext;
     
    
   

    

     

    
    

     

      }ListNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      ListNode* Meeting_node(ListNode* pHead);
     
    
   

    

     

    
    

     

      ListNode* Enter_node(ListNode* pHead);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ListNode* pHead  = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode1 = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode2 = NULL;
     
    
   

    

     

    
    

     

          ListNode* pNode3 = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          ListNode* pThis = NULL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

          pHead = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode1 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode2 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pNode3 = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     

          pThis = (ListNode*)malloc(sizeof(ListNode));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	if (pHead == NULL || pNode1 == NULL || pNode2 == NULL || pNode3 == NULL || pThis == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cout << "malloc fail" << endl;
     
    
   

    

     

    
    

     
		return ;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pHead->m_nValue = 0;
     
    
   

    

     

    
    

     

      	pHead->m_pNext  = pNode1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode1->m_nValue = 1;
     
    
   

    

     

    
    

     

      	pNode1->m_pNext  = pNode2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode2->m_nValue = 2;
     
    
   

    

     

    
    

     

      	pNode2->m_pNext  = pNode3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	pNode3->m_nValue = 3;
     
    
   

    

     

    
    

     

      	pNode3->m_pNext  = pNode1;	//构成一个环 0 -> 1 -> 2 -> 3 -> (1) -> ....
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 	
     
    
   

    

     

    
    

     

       	pThis = Enter_node(pHead);
     
    
   

    

     

    
    

     

       	cout << "enter node:" << pThis->m_nValue << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：取环中任一节点
     
    
   

    

     

    
    

     

      //输入：pHead 链表头节点指针
     
    
   

    

     

    
    

     

      //返回：目标节点指针
     
    
   

    

     

    
    

     

      ListNode* Meeting_node(ListNode* pHead)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.检查输入参数的合法性
     
    
   

    

     

    
    

     
	if (NULL == pHead)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	ListNode* pSlow = pHead;
     
    
   

    

     

    
    

     

      	ListNode* pFast = pHead->m_pNext;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.找出环内某节点
     
    
   

    

     

    
    

     
	while ((pSlow->m_pNext != NULL) && (pFast->m_pNext != NULL))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (pSlow == pFast)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			return pFast;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      		pSlow = pSlow->m_pNext;		//偏移1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      		pFast = pFast->m_pNext;		//偏移2
     
    
   

    

     

    
    

     
		if (pFast->m_pNext != NULL)	
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			pFast = pFast->m_pNext;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.没有环结构
     
    
   

    

     

    
    

     
	return NULL;
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：取环的入口节点
     
    
   

    

     

    
    

     

      //输入：pHead 链表头节点指针
     
    
   

    

     

    
    

     

      //返回：目标节点指针
     
    
   

    

     

    
    

     

      ListNode* Enter_node(ListNode* pHead)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.检查输入参数的合法性
     
    
   

    

     

    
    

     
	if (NULL == pHead)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	ListNode* pNode1 = Meeting_node(pHead);
     
    
   

    

     

    
    

     

      	ListNode* pNode2 = pNode1->m_pNext;
     
    
   

    

     

    
    

     
	int count = 1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.统计环的节点个数count
     
    
   

    

     

    
    

     
	while (pNode1 != pNode2)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		++count;
     
    
   

    

     

    
    

     

      		pNode2 = pNode2->m_pNext;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.找出入口节点
     
    
   

    

     

    
    

     

      	pNode1 = pHead;
     
    
   

    

     

    
    

     

      	pNode2 = pHead;
     
    
   

    

     

    
    

     
	for (int i = 0;i < count;i++)
     
    
   

    

     

    
    

     

      	{//调整pNode1 pNode2的相对位置
     
    
   

    

     

    
    

     

      		pNode2 = pNode2->m_pNext;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	while (pNode1 != pNode2)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		pNode1 = pNode1->m_pNext;
     
    
   

    

     

    
    

     

      		pNode2 = pNode2->m_pNext;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//4.返回环入口指针
     
    
   

    

     

    
    

     
	return pNode1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98722797