给定一个链表，检查链表是否有循环。下图显示了带有循环的链表。

image

解题思路

使用快慢两个指针遍历链表。
将慢指针（slow_p）一次移动一个节点，另快指针（fast_p）移动两个。 如果这些指针在同一节点相遇，则存在循环。如果指针不符合，则链接列表没有循环。

image.png

原理分析

1）当慢指针进入循环时，快指针已在循环内部。令快指针与慢指针的距离为k。

2）现在，如果考虑慢慢指针的移动，我们可以注意到它们之间的距离在每次迭代后增加一。经过一个迭代（慢指针=慢指针的下一个节点，快指针=快指针的下一个节点），快慢指针的距离变为k + 1，经过两次迭代为k + 2，依此类推。当距离变为环的长度n时，它们将会合，因为它们在长度为n的环中运动。

例如，我们可以在下图中看到，初始距离为2。经过1次迭代，距离变为3，经过2次迭代，距离变为4。经过3次迭代，它变为距离0的5。它们相遇。

代码实现

// Java代码检测list是否成环 
class LinkedList { 
   Node head; // head of list 
 
   /* Linked list 节点*/
   class Node { 
       int data; 
       Node next; 
       Node(int d) 
       { 
           data = d; 
           next = null; 
       } 
   } 
 
   /* 添加新节点至链表头 */
   public void push(int new_data) 
   { 
       /* 1 & 2: 分配节点空间 & 
                 设置数据*/
       Node new_node = new Node(new_data); 
 
       /* 3. 将新节点的next指向head节点 */
       new_node.next = head; 
 
       /* 4. head指向新节点 */
       head = new_node; 
   } 
 
   int detectLoop() 
   { 
       Node slow_p = head, fast_p = head; 
       while (slow_p != null && fast_p != null && fast_p.next != null) { 
           slow_p = slow_p.next; 
           fast_p = fast_p.next.next; 
           if (slow_p == fast_p) { 
               System.out.println("Found loop"); 
               return 1; 
           } 
       } 
       return 0; 
   } 
 
   /* 测试驱动程序 */
   public static void main(String args[]) 
   { 
       LinkedList llist = new LinkedList(); 
 
       llist.push(20); 
       llist.push(4); 
       llist.push(15); 
       llist.push(10); 
 
       /*Create loop for testing */
       llist.head.next.next.next.next = llist.head; 
 
       llist.detectLoop(); 
   } 
} 

输出:

Found Loop

时间复杂度：O(n)
空间复杂度：O(1)