算法小知识------10.16----关于链表的相关算法(1)
判断一个链表是否有环
(×)冒泡式循环，每到新的下一个节点，就重新对之前走过的节点做遍历，查看是否有重复，有则证明有循环
假设节点数量为n，则该解法时间复杂度为O(n²)，但是没有创建额外的空间，所以空间复杂度为O(1)
(×)创建以节点的值作为KEY的HashSet，存储已经走过的节点，如果新的节点已经被存过，说明有环；与上述方法类似，但是额外创建了HashSet
假设节点数量为n，则该解法时间复杂度为O(n)，由于额外开辟了空间使用，所以空间复杂度为O(n)
(√)以双指针形式指向链表头，指针A，每次移动1个节点；指针B，每次移动2个节点；循环指针，如果指针相同，则代表有环，反之则继续循环
实现
/** * 判断是否有环 * * @param head 链表头节点 */ public static boolean isCycle(ListNode head){ ListNode p1 = head; ListNode p2 = head; while(p2 != null && p2.next != null){ p1 = p1.next; p2 = p2.next.next; if(p1 == p2){ return true; } } return false; }原理：数学上的追及问题，在操场上跑步，A的速度比B快；同一起跑线，一段时间后，A必然会再次追上B；因为跑道是环形的
假设节点数量为n，则该算法的时间复杂度为O(n)，除了两个指针，没有使用额外的储存空间，所以空间复杂度是O(1)
作者：Jayhaw_花
链接：https://juejin.cn/post/7019560409950584845