leetcode 241题,环形链表。https://leetcode.cn/problems/linked-list-cycle/
1、哈希表
建立一个哈希表,每次访问的节点都存储起来。如果某个节点在哈希表中已存在,说明有环。时间复杂度O(n),空间复杂度o(n)
2、双指针之快慢指针
快指针每次移动2个节点,慢指针每次移动1个节点。如果有环,快指针会一直在环里,两个指针一定能相遇。反之无环,快指针会先到达终点。时间复杂度O(n),空间复杂度o(1)
哈希表的实现比较简单,且空间复杂度高,此处仅给出更加合适的双指针代码。
python3
def has_cycle(head: Optional[ListNode]) -> bool: slow, fast = head, head # 快指针每次走两步,即fast.next.next。None没有next属性,所以当fast为None或者fast.next为None时,都会报错。 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False
JavaScript
function hasCycle(head) { let slow = head; let fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow === fast) { return true; } else {}; // 此处是为了代码规范可读 }; return false; }