Fast and slow pointers

The Fast & Slow pointer approach is a pointer algorithm that uses two pointers which move through the array at different speeds. This approach is quite useful when dealing with cyclic LinkedLists or arrays.

By moving at different speeds, the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

Given the head of a Singly LinkedList, write a function to determine if the LinkedLists has a cycle in it or not.

If the LinkedList has a cycle, the fast pointer enters the cycle first, followed by the slow pointer. After this, both pointers will keep moving in the cycle infinitely. If at any stage both of these pointers meet, we can conclude that the LinkedList has a cycle in it.

Here is what our algorithm will look like:

class Node {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}
function has_cycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

Time complexity

As we have concluded above, once the slow pointer enters the cycle, the fast pointer will meet the slow pointer in the same loop. Therefore, the time complexity of our algorithm will be O(N) where N is the total numbers of nodes in the LinkedList.

Space complexity

The algorithm runs in constant space O(1)

Given the head of a LinkedList with a cycle, find the length of the cycle.

We can use the above solution to find the cycle in the LinkedList. Once the fast and slow pointers meet, we can save the slow pointer and iterate the whole another pointer until we see the slow pointer again to find the length of the cycle.

function find_cycle_length(head){
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow === fast) {
      return calculate_cycle_length(slow);
    }
  }
  return 0;
}
function calculate_cycle_length(slow) {
  let current = slow;
  let cycle_length = 0;
  
  while (true) {
    current = current.next;
    cycle_length++;
    if (current === slow) {
      break;
    }
  }
  return cycle_length;
}

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

1 Take two pointers: slow and fast

2 Initialize both pointers to the start of the LinkedList

3 We can find the length of the LinkedList cycle using the approach above. Let’s assume that the length of the cycle is “K”

4 Move back the slow pointer to the beginning

5 Move both slow and fast 1x speed

6 As fast is “K” nodes ahead of slow, which means fast must have complete one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle.

function find_start(head) {
  if (!head || !head.next) return null;
 
  let slow = head.next;
  let fast = head.next.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

Happy Number

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.
• Return true if n is a happy number, and false if not. For example: 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4

If the number is a happy number, the process will be stuck in a cycle on number ‘1,’ and if the number is not a happy number then the process will be stuck in a cycle with a set of numbers.

Each number will definitely have a cycle. Therefore, we will use the same fast & slow pointer strategy to find the cycle and once the cycle is found, we will see if the cycle is stuck on number ‘1’ to find out if the number is happy or not.

function find_happy_number(num) {
  let slow = num;
  let fast = num;
  while (true) {
    slow = find_square_sum(slow);
    fast = find_square_sum(find_square_sum(fast));
    if (slow === fast) {
      break;
    }
  }
  return slow === 1;
}
function find_square_sum(num) {
  let sum = 0;
  while (num > 0) {
    digit = num % 10;
    sum += digit * digit;
    num = Math.floor(num / 10);
  }
  return sum;
}