/**
* 解法一:双指针
* 思路:
* (1)设置快慢两个指针,初始都指向链表头。
* (2)遍历链表,快指针每次走两步,慢指针每次走一步。
* (3)如果快指针到了链表末尾,说明没有环,因为它每次走两步,所以要验证连续两步是否为 NULL。
* (4)如果链表有环,那快慢双指针会在环内循环,因为快指针每次走两步,因此快指针会在环内追到慢指针,二者相遇就代表有环。
* 时间复杂度: O(n),最坏情况下遍历链表n个节点
* 空间复杂度: O(1),仅使用了两个指针,没有额外辅助空间
*/
export function hasCycle(head: ListNode | null): boolean {
if (head == null) return false
// 快慢双指针
let fast: ListNode = head
let slow: ListNode = head
while (fast != null && fast.next != null) { // 快指针移动两步
fast = fast.next.next // 慢指针移动一步
slow = slow.next // 相遇则有环
if (fast === slow) return true
}
return false // 到末尾则没有环
};
/**
* 解法二:哈希
* 思路:
* (1)使用哈希表来存储所有已经访问过的节点。
* (2)每次我们到达一个节点,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中。
* (3)重复这一过程,直到我们遍历完整个链表即可。
* 时间复杂度: O(n),最坏情况下遍历链表 n 个节点
* 空间复杂度: O(n),其中 n 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。
*/
export function hasCycle(head: ListNode | null): boolean {
if (head == null) return false
const seenMap = new Map()
while (head != null) {
if (seenMap.has(head)) return true
seenMap.set(head, 1)
head = head.next
}
return false
};
一站式解决前端面试高频算法题