AI solution for JavaScript Coding Question on BFE.dev
100. detect circle in linked list

To detect a circle in a linked list, we can use the "slow and fast pointer" approach. We maintain two pointers, slow and fast. Initially, both pointers are set to the head of the linked list. Then we move the slow pointer one step at a time and the fast pointer two steps at a time. If the fast pointer catches up to the slow pointer, it means there is a circle in the linked list.

Here's the implementation in JavaScript:

function hasCircle(head) {
  let slow = head
  let fast = head

  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      return true
    }
  }
  return false
}

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The space complexity is O(1), since we are only using two pointers to scan the list.

To solve it without extra space, we can also use the "reverse the list" approach. We can traverse the linked list and keep track of the previous node for each node. If we encounter a node whose previous node points to a later node, it means there is a circle in the linked list.

Here's the implementation in JavaScript:

function hasCircle(head) {
  let prev = null
  let curr = head

  while (curr) {
    let next = curr.next
    curr.next = prev
    prev = curr
    curr = next

    if (prev && prev.next && prev.next.val >= prev.val) {
      return true
    }
  }
  return false
}

The time complexity of this algorithm is also O(n), but the space complexity is O(1), since we are mutating the linked list in place. However, this approach has the side effect of modifying the original linked list, which may not be desirable.