Loveyless的学习笔记

Appearance

Return to top
On this page

解题

你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

哈希表实现

遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

typescript
function hasCycle(head: ListNode | null): boolean {
  let map = new Map();
  while (head) {
    if (map.has(head)) {
      return true;
    }
    map.set(head, head);
    head = head.next;
  }
  return false;
}

时间复杂度 O(n),最坏需要遍历整个链表

空间复杂度 O(n),最坏情况下我们需要将每个节点插入到哈希表中一次

快慢指针

题解链接

typescript
//快慢指针
function hasCycle3(head: ListNode | null): boolean {
  if (!head || !head.next) return false;

  let cur1 = head;
  let cur2 = head.next;

  while (cur2) {
    //如果快指针是最后一个了 说明没有环
    if (!cur2.next) return false;
    //如果遇到了 说明有环
    if (cur1 == cur2) return true;
    cur1 = cur1.next;
    cur2 = cur2.next.next;
  }
  return false;
}

感想

哈希表我倒是想出来了 快慢指针确实巧妙