LeetCode 142

概述

• 在一个链表中，确定是否有环。如果有，确定环的起始结点位置

思路

• 确定有环：快慢指针法

• 确定环起始位置：

  (x+y)*2=(x+y)+n(y+z)	//这里n(y+z)是快指针多走的
  x=n(y+z)-y=(n-1)(y+z)+z	//x是我们要求的
  注意到（n-1)(y+z)是环的长度，z、x分别拿出来看就可知道如何找到入口

  ---

  class Solution {
  public:
      ListNode *detectCycle(ListNode *head) {
          if(head==NULL) return NULL;
          ListNode* slow=head;
          ListNode* fast=head;
          int flag=0;
          while(fast != NULL && fast->next != NULL){	//注意判断
              slow=slow->next;	//慢指针
              fast=fast->next->next;	//快指针
              if(slow==fast){ //有环
                  flag=1;
                  break;
              }    
          }
          //这部分，可以直接放在前面的if里面的
          if(flag==0) return NULL;
          ListNode* temp=head;
          while(temp!=fast){
              fast=fast->next;
              temp=temp->next;
          }
          return temp;
      }
  };