2.5 Floyd链表查环算法

文章目录原理Node代码List类代码测试代码复杂度分析原理链表查环是一个笔试面试热门题目但是我完结这个专栏时没写。链表查环有几种常见的方法一个办法是使用hash map或hash set来记录已经访问过的节点这个方法的缺点是空间复杂度高。其余的方法比如节点加是否已访问属性缺点也是如此。著名的计算机算法科学家Floyd发明了一个算法使用了两个指针一个快指针和一个慢指针。快指针一次走两步慢指针一次走一步如果存在环这两个指针一定会相遇。这原理很简单就是个小学数学题在圆形的跑道上存在速度差一定会相遇。在环上不存在小数所以速度差为1才会最终相遇。所以慢指针一次走两步快指针一次走三步也是会相遇的。但最简洁的是速度1和速度2的快慢组合。因为快慢指针的原因这个算法也叫龟兔算法tortoise and the hare algorithm。Node代码packagecom.youngthing.list.linked;/** * 2022/1/9 22:17 创建 * * author 花书粉丝 */publicclassNodeT{privateNodeTprev;privateNodeTnext;privateTkey;publicNode(Tvalue){keyvalue;}publicNodeTgetPrev(){returnprev;}publicvoidsetPrev(NodeTprev){this.prevprev;}publicNodeTgetNext(){returnnext;}publicvoidsetNext(NodeTnext){this.nextnext;if(next!null){next.prevthis;}}publicTgetKey(){returnkey;}publicvoidsetKey(Tkey){this.keykey;}}List类代码packagecom.youngthing.list.linked;/** * 2022/1/9 22:17 创建 * * author 花书粉丝 */publicclassLinkedListT{privateNodeThead;privateNodeTtail;privateintlength;publicvoidaddLast(Tvalue){NodeTnodenewNode(value);addLast(node);}publicvoidaddLast(NodeTnode){if(headnull){tailheadnode;}else{tail.setNext(node);tailnode;}length;}publicTremoveLast(){if(headnull){thrownewRuntimeException(链表为空);}Ttemptail.getKey();if(length1){tailheadnull;returntemp;}else{tailtail.getPrev();}length--;returntemp;}publicvoidaddFirst(Tvalue){NodeTnodenewNode(value);if(headnull){tailheadnode;}else{node.setNext(head);headnode;}length;}publicTremoveFirst(){Ttemphead.getKey();if(length1){tailheadnull;}else{headhead.getNext();}length--;returntemp;}publicbooleanfloyd(){NodeTslowhead;NodeTfasthead;while(slow!nullfast!nullfast.getNext()!null){slowslow.getNext();fastfast.getNext().getNext();if(slowfast){returntrue;}}returnfalse;}}测试代码packagecom.youngthing.list.test.linked;importcom.youngthing.list.linked.LinkedList;importcom.youngthing.list.linked.Node;/** * Floyd测试 * created at 02/06/2022 * * author 花书粉丝 * a hrefmailto://yujianbochtwm.comyujianbochtwm.com/a * since 1.0.0 */publicclassFloydTest{publicstaticvoidmain(String[]args){finalLinkedListIntegerlistnewLinkedList();finalNodeIntegern1newNode(1);finalNodeIntegern2newNodeInteger(2);finalNodeIntegern3newNodeInteger(3);finalNodeIntegern4newNodeInteger(4);finalNodeIntegern5newNodeInteger(5);finalNodeIntegern6newNodeInteger(6);finalNodeIntegern7newNodeInteger(7);list.addLast(n1);list.addLast(n2);list.addLast(n3);list.addLast(n4);list.addLast(n5);list.addLast(n6);list.addLast(n7);list.addLast(n2);System.out.println(list.floyd());}}测试结果为true代表存在环。复杂度分析存在环的链表只有一个模式就是链表加上一个环形成一个数字6的形状。假设这个6字形链表段长度为a环段的长度为b。慢指针走完链表段时到达环段和链表段的交点时快指针已经走了2 a 2a2a的距离。因为速度差为1所以根据小学的应用题公式所以在慢指针再跑一个b − a b-ab−a长度后相遇。假设慢指针还要跑环之前的链表段长度a aa。这两段加起来刚好是链表的总长度n所以总时间复杂度就是O ( n ) O(n)O(n)。空间复杂度就是两个指针所占的空间所以空间复杂度为O ( 1 ) O(1)O(1)。