Linked List Cycle Easy 0 attempts
LeetCode ↗

Linked List Cycle

Easy Linked List LeetCode

Given the head of a linked list, figure out whether it loops back on itself anywhere — that is, whether repeatedly following next pointers eventually revisits a node you've already seen. Return true if such a loop exists and false if the list simply ends. Aim for a solution that uses only O(1) extra memory.

Input Format
Implement linkedListCycle(head). Inputs below show JavaScript function arguments; there is no stdin parsing. headFixture is [values, pos]; the tail links to the zero-based pos, or null when pos is -1. The function receives only the head.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
headFixture = [[3,2,0,-4],1]
Output
true

Example 2

Input
headFixture = [[1],-1]
Output
false
Constraints
  • 0 to 10^4 nodes
  • -10^5 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[[3,2,0,-4],1]] Expected: true
Case 2
Args: [[[1],-1]] Expected: false
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.

javascript
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.

JavaScript