判断链表是否有环

判断链表是否有环

一种思路是暴力hash：遍历整个链表，每次判断指针的hash值是否在hash表中，如果有说明有重复的节点，有环；如果没有，hash后放入表中继续遍历。时间复杂度是O(n),但空间复杂度也是O(n)。
另一个思路是使用快慢指针： 设置slow，fast。初始指向表头，slow移动步长为1， fast移动步长为2。每次移动后都进行比较，如果相等则证明有环，如果fast到达NULL，则说明没有环。

LNode* hasLoop(LinkList  head)
{
  if(head == NULL || head->next == NULL)
    return NULL;

  LNode* slow = head->next;
  LNode* fast = head->next;
  
  while(fast && fast->next)
  {
    slow = slow->next;
    fast = fast->next->next;
    if(slow == fast) //有环
      return slow; 
  }
return NULL
}

续： 如何找到环的入口

一个指针从头开始，一个指针从相遇点开始，步长各为1。相遇点就是入口。

LNode* findEntrance(LinkList head)
{
  LinkNode* start = head->next;
  LinkNode * meet = hasLoop(head);

  while(start != meet) // 相遇就退出
  {
    start = start->next;
    meet = meet->next;
  }
  return start;

}