【证明】判断链表存在环——快慢指针一定能相遇_快慢指针判断链表环数学证明

问题

在面试题中常有这样的考察链表题目：

如何判断一个链表中存在环？

思路

常见的有3个思路：

• 1、暴力遍历
  时间复杂度：O(n^2)
空间复杂度：O(1)
  双重遍历，外循环依次遍历每个结点；内循环用新指针从头遍历此结点之前的所有结点，判断是否有相同结点。

• 2、hash存储遍历过的结点
  时间复杂度：O(n)
空间复杂度：O(n)
  只需遍历一轮，每次遍历完一个结点将其加入hash_map，遍历时从hash_map中判断是否已经出现过。由于hash_map存取时间O(1)，所以用牺牲空间换时间的方法可以把时间降到O(n)。

• 3、快慢指针
  时间复杂度：O(n)
空间复杂度：O(1)
  神奇的快慢指针法可以不另外开辟空间的同时只需要一轮遍历就可以判断环的存在。

  具体思路：
  使用一快一慢2个指针，均指向头结点。慢指针p1以每一步移动一个结点的速度前进，快指针p2一步移动2个结点。

  (1) 若不存在环：
  p1、p2均会到达链表尾部NULL，判断结束。

  (2) 若存在环：可以把环看作操场跑道，把慢指针p1看作龟

  声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/64499