算法小知识------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