数据结构与算法 | Leetcode 141:Linked List Cycle

前面，我们实现了链表的 反转 操作，本篇来聊聊，如何检测单链表中的环。链表环检测Leetcode 141: Linked List Cycle有两种方法来解决这个问题：使用Hashing思路定义一个Map，当循环遍历Linked List时，依次将Node放入Map中，等到循环到下一轮时，检查Node是否存在于Map中，若存在则表示有环存在。实现/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } /public class Solution { public boolean hasCycle(ListNode head) { Map map = new IdentityHashMap(); for(ListNode x = head; x != null;){ if(map.containsKey(x)){ return true; } map.put(x, null); x = x.next; } return false; }}Floyd判圈算法Floyd判圈算法如果有限状态机、迭代函数或者链表上存在环，那么在某个环上以不同速度前进的2个指针)必定会在某个时刻相遇。同时显然地，如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇，那么可以判定存在一个环，且可以求出2者相遇处所在的环的起点与长度。从Linked List的Head节点出发，我们定义两个移动指针，一个的移动速度为每次前进一个节点，另一个每次前进两个节点。然后判断这两个指针移动后的结果是否相等。代码/* * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ return true; } } return false; }}这两种方式的时间复杂度均为O(n)，空间复杂度均为O(1).参考资料https://www.geeksforgeeks.org…https://marcin-chwedczuk.gith…Floyd判圈算法《数据结构与算法之美》