Fast and slow pointers

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;
}

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;
}
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;
}
  • 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
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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store