JSFiddle - React, Tailwind, and code Playground

by asdf

JavaScript

// Find a cycle in linked list: a) find if there is cycle in linked list b) find beginning of the cycle

function findCycle(head) {
	var slow = head;
  var fast = head.next;
  var next, count;
  while (fast && fast.next) {
  	if (slow === fast) {
    	// there is a cycle
      // count elements in this cycle
      count = 1;
      next = slow.next;
      while ( slow !== next) {
      	count++;
        next = next.next;
      }
      // set new pointers to find a start of the cycle
      slow = head;
      fast = head;
      while (count) {
      	fast = fast.next;
        count--;
      }
      // get start element
      while (slow !== fast) {
      	slow = slow.next;
        fast = fast.next;
      }
    	return slow.value;
    }
    slow = slow.next;
    fast = fast.next.next;
  }
}

var list = createLinkedList(8, 4);
console.log(findCycle(list));
var list2 = createLinkedList(8);
console.log(findCycle(list2));
var list3 = createLinkedList(5, 2);
console.log(findCycle(list3));

function createLinkedList(n, cycle) {
  var head = {};
  var current = head;
  var prev;
  var cycleStart;
  var i=1;
  while (i<n) {
  	if (cycle && i===cycle) {
    	cycleStart = current;
    }
    current.value = i;
    prev = current;
    current = {};
    prev.next = current;
    i++;
  }
  current.value = i;
  if (cycle) {
  	current.next = cycleStart;
  }
  return head;
}