剑指offer之找到链表里面包含环的入口节点

1 问题

剑指offer之找到链表里面包含环的入口节点，比如

  

   

    

     

    
    

     

       // node7<-node6 <-node5
     
    
   

    

     

    
    

     

       // | |
     
    
   

    

     

    
    

     

       //head->node1->node2->node3->node4
     
    
  
 

环的入口节点是node2

2 代码实现

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define true 1
     
    
   

    

     

    
    

     

      #define false 0 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int value;
     
    
   

    

     

    
    

     
 struct node *next;
     
    
   

    

     

    
    

     

      } Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       *得到环的第一个公共节点
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      Node *getCommonNode(Node *head)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if (head == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 return NULL;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Node *first = NULL;
     
    
   

    

     

    
    

     

       Node *second = NULL;
     
    
   

    

     

    
    

     

       first = head;
     
    
   

    

     

    
    

     

       second = head;
     
    
   

    

     

    
    

     
	int isCircle = false;
     
    
   

    

     

    
    

     
	//判断是否有环
     
    
   

    

     

    
    

     
 while (second != NULL && (second->next) != NULL && (second->next->next != NULL))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       first = first->next;
     
    
   

    

     

    
    

     

       second = second->next->next;
     
    
   

    

     

    
    

     
 if (first == second)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       isCircle = true;
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
	if (isCircle == false)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("the list do not circle\n");
     
    
   

    

     

    
    

     
		return NULL;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//判断环的大小,这个时候肯定是进到环里面去了
     
    
   

    

     

    
    

     
	int len = 0;
     
    
   

    

     

    
    

     

      	first = first->next;
     
    
   

    

     

    
    

     

      	++len;
     
    
   

    

     

    
    

     
	while (first != second)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		len++;
     
    
   

    

     

    
    

     

      		first = first->next;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     
	//求出入口节点
     
    
   

    

     

    
    

     

      	Node *start = head;
     
    
   

    

     

    
    

     

      	Node *end = head;
     
    
   

    

     

    
    

     
	while (len-- > 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		end = end->next;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	while (start != end)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		start = start->next;
     
    
   

    

     

    
    

     

      		end = end->next;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return start;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       Node *head = NULL;
     
    
   

    

     

    
    

     

       Node *node1 = NULL;
     
    
   

    

     

    
    

     

       Node *node2 = NULL;
     
    
   

    

     

    
    

     

       Node *node3 = NULL;
     
    
   

    

     

    
    

     

       Node *node4 = NULL;
     
    
   

    

     

    
    

     

       Node *node5 = NULL;
     
    
   

    

     

    
    

     

       Node *node6 = NULL;
     
    
   

    

     

    
    

     

       Node *node7 = NULL;
     
    
   

    

     

    
    

     

       head = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node1 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node2 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node3 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node4 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node5 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node6 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

       node7 = (Node *)malloc(sizeof(Node));
     
    
   

    

     

    
    

     
 if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL
     
    
   

    

     

    
    

     

       || node4 == NULL || node5 == NULL || node6 == NULL || node7 == NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("malloc fail\n");
     
    
   

    

     

    
    

     
 return false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
	// node7<-node6 <-node5
     
    
   

    

     

    
    

     
 // | |
     
    
   

    

     

    
    

     
 //head->node1->node2->node3->node4
     
    
   

    

     

    
    

     

       head->value = 0;
     
    
   

    

     

    
    

     

       head->next = node1;
     
    
   

    

     

    
    

     

       node1->value = 1;
     
    
   

    

     

    
    

     

       node1->next = node2;
     
    
   

    

     

    
    

     

       node2->value = 2;
     
    
   

    

     

    
    

     

       node2->next = node3;
     
    
   

    

     

    
    

     

       node3->value = 3;
     
    
   

    

     

    
    

     

       node3->next = node4;
     
    
   

    

     

    
    

     

       node4->value = 4;
     
    
   

    

     

    
    

     

       node4->next = node5;
     
    
   

    

     

    
    

     

       node5->value = 5;
     
    
   

    

     

    
    

     

       node5->next = node6;
     
    
   

    

     

    
    

     

       node6->value = 6;
     
    
   

    

     

    
    

     

       node6->next = node7;
     
    
   

    

     

    
    

     

       node7->value = 7;
     
    
   

    

     

    
    

     

       node7->next = node2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       Node *result = getCommonNode(head);
     
    
   

    

     

    
    

     
 if (result != NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("the first common value is %d\n", result->value);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("list do not have circle\n");
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return true;
     
    
   

    

     

    
    

     

      }
     
    
  
 

3 运行结果

the first common value is 2
 

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

原文链接：chenyu.blog.csdn.net/article/details/88046277