Skip to content

传送门

141. 环形链表

image.png

快慢指针

image.png

typescript
// JS
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;
    }
  }
  // 如果快指针 reaches 到链表末端,说明链表无环
  return false;
}

哈希

image.png

typescript
var hasCycle = function (head) {
    if (head === null) return false;

    let set = new Set();
    while (head) {
        if (set.has(head)) return true;

        set.add(head);
        head = head.next;
    }

    return false;
};