算法思想一:双指针
解题思路:
我们使用两个指针,fast 与 slow。
它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。
图解:
代码展示:
Python版本
class Solution: def hasCycle(self , head ): # write code here if not head: return head # 双指针 快慢指针 slow = head fast = head while slow and fast: slow = slow.next if fast.next: fast = fast.next.next else: return False # 当双指针相遇 即表示指针有环 if slow == fast: return True return False
复杂度分析:
时间复杂度O(N):其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度
空间复杂度O(1):额外使用的指针占用常数空间
算法思想二:哈希表
解题思路:
我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希表可以很方便地实现
1、遍历链表,并将访问过的结点存储到哈希表中
2、判断结点是否在哈希表中,若存在则返回 true
3、遍历结束,则返回 false
代码展示:
JAVA版本
public class Solution { public boolean hasCycle(ListNode head) { ListNode pos = head; // 哈希表记录访问过的结点 Set<ListNode> visited = new HashSet<ListNode>(); while (pos != null) { // 判断结点是否被访问 if (visited.contains(pos)) { return true; } else { // 结点记录添加到哈希表中 visited.add(pos); } // 遍历 pos = pos.next; } return false; } }
复杂度分析:
时间复杂度O(N):其中 N 为链表中节点的数目。遍历整个链表的结点
空间复杂度O(N):其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。