单链表是否存在环

面试题：如何检测一个单链表是否有环？如果有环的入口在哪里？

题目描述：单链表有环指的是单链表中某个结点的next域指针指向的是链表中的某一个结点，这样在链表的尾部就形成了一个环形结构。如何判断单链表有环？如果有，怎么确定环入口？

分析与解答：
方法一：蛮力法
定义一个hash_set来存放结点的指针，并将其初始化为空，从链表头指针开始向后遍历，每次遇到一个指针就判断它在hash_set中是否存在，如果不存在，说明这个结点是第一次访问，还没有形成环。那么久将它加入到hash_set中，如果hash_set 中找到了同样的指针，那么久说明他已经被访问过了，于是就有环，第一个已经存在的结点就是环的入口。
这个方法的时间复杂度和空间复杂度都为O(N)。

方法二：快慢指针遍历
定义两个指针fast和slow，两者初始值都指向链表头，指针slow一次走一步， fast 指针每次走两步，两个指针同时向前移动，快指针和慢指针每次移动都要进行对比。如果两个相等，则证明有环，如果快指针走到了链表尾部还没相遇，说明不存在环。
重要：如何判断环的入口？
如果链表有环，那么上面的方法的思路。当走的快的指针fast 与走的慢的指针，slow相遇时，slow指针肯定没有遍历完链表。而fast 已经在环内循环了n圈（n>=1）。如果slow指针走了s步，那么fast走了2s步了，（fast的步数还等于s, 加上多转的n圈的）。
假设环长为r，那么就可以得到：

2s = s + nr
快指针 = 慢指针 + 已经转过的n圈
所以：
s = nr

假设这个链表总长为L，环入口点与链表头的距离为a, 与相遇点的距离为x。那么，

a + x = s = nr
而整个环长的r 又等于 L - a 
所以转换后得到：
a+x  = (n-1)r + r =  (n-1)r + (L-a)
a+x = (n-1)r + L -a
a = (n-1)r + (L -a  -x)
L - a - x 是相遇点往后 的方向上与环入口的距离。

从链表的头到环入口点的距离= （n-1）* 环长 + 相遇点到环入口的距离。于是从链表头与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，并且相遇点为环的入口所以。
所以代码实现如下：

#include <stdlib.h>    
#include <iostream>    
    
using namespace std;    
    
typedef struct LNode {    
  int value;    
  struct LNode* next;    
}LNode, *LinkList;    
        
// 构造一个结点
LinkList CreateNode(int value) {                                                         
  LinkList head = (LinkList)malloc(sizeof(LNode));                                       
  head->value = value;                                                                   
  head->next = NULL;  
  return head;                                                                   
} 
// 输出链表
void PrintList(LinkList head) {                                                          
  LinkList tmp = head;                                                                   
  cout << "list: head -> ";                                                              
  while(tmp != NULL) {                                                                   
    cout << tmp->value << " -> ";                                                        
    tmp = tmp->next;                                                                     
  }                                                                                      
  cout << endl;                                                                          
}


// 带头结点的链表
// 返回NULL表示无环, 否则返回相遇点
LinkList IsLoop(LinkList head) {
  if (head == NULL || head->next == NULL)
    return NULL;

  LinkList fast = head->next;
  LinkList slow = head->next;
  while (fast != NULL && fast->next != NULL) {
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow) {
      return slow;
    }
  }
  return NULL;
}

// 是否有环，有环则找到入口结点
LinkList FindLoopEntry(LinkList head) {
  LinkList meet_node = IsLoop(head);
  if (meet_node == NULL)
    return NULL;

  LinkList first = head->next;

  while (meet_node != first) {
    meet_node = meet_node->next;
    first = first->next;
  }

  return first;
}

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

  LinkList head = CreateNode(-1);

  LinkList tmp = NULL;
  LinkList last = head;

  for (int i = 1; i < 9; ++i) {
    tmp = CreateNode(i);

    last->next = tmp;
    last = tmp;
  }

  cout << "orig list: head -> ";
  PrintList(head->next);

  // 无环
  if ((tmp = FindLoopEntry(head)) == NULL) {
    cout << "list is not loop" << endl;
  }

  // 有环
  last->next = head->next->next->next->next;

  tmp = head->next;
  int count = 10;
  cout << "loop list: head -> ";
  while(tmp != NULL && count-- > 0) {
    cout << tmp->value << " -> ";
    tmp = tmp->next;
  }
  cout << endl;

  if ((tmp = FindLoopEntry(head)) != NULL) {
    cout << "list has loop. Loop entry Node is:"
        << tmp->value << endl;
  }
  return 0;
}

运行结果：

链表有环运行结果.png

最后编辑于：2019.11.26 15:33:48