Linked List Cycle | Problems

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer. Return true if there is a cycle, otherwise return false. Solve it using O(1) extra memory.

Example 1:

Input: head = [3,2,0,-4], pos = 1 (tail connects to index 1)
Output: true

Example 2:

Input: head = [1], pos = -1
Output: false

Sample Input

—

Sample Output

—

Constraints

0 to 10^4 nodes
-10^5 <= Node.val <= 10^5

Topics

Linked List

Approach: Floyd's Tortoise and Hare

Use two pointers: slow moves one step at a time, fast moves two steps. If the list has a cycle, the fast pointer will eventually meet the slow pointer. If fast reaches null, there is no cycle.

function linkedListCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Time Complexity: O(n)

Space Complexity: O(1)

Saved in this browser only. Private to you.