CODEWITHSUNDEEP
javascriptlinked-list
Rajat Bansal
Rajat Bansal

Reputation: 183

Finding a cycle in singly linked list with javascript (Is my solution efficient)

My solution works well if the starting node is passed to the function correctly. I want to know if my solution is good and efficient. I should be able to return true if the cycle exists via function to which first node is passed as parameter. I would like to know if my solution is efficient especially for an interview setting. My comments in the code are self explanatory. Im using a variable track to traverse through the list and checking for a null or head as the next. If i encounter any of them traversal ends and then individually i check for null or head condition and based on that i return the appropriate boolean value.

function SLLNode(elem) {
    this.value=elem;
    this.next=null;
}

var hasCycle=function(node){

    var track=node;
    //traverse thru list till next node is either null or back to first node
    while(track.next!==null && track.next!==this.head){
        track=track.next;
    }
    if(track.next === null){ //if next node null then no cycle
        return false;
    }
    if(track.next===this.head){ //if next node head then there is cycle
        return true;
    }
}

var my_node1=new SLLNode(3);
var my_node2=new SLLNode(5);
var my_node3=new SLLNode(19);

//assigning head
var head=my_node1;

//connecting linked list
my_node1.next=my_node2;
my_node2.next=my_node3;
my_node3.next=my_node1; //cycle
console.log("Has cycle?: "+hasCycle(my_node1)); //outputs true as expected

var node1=new SLLNode(3);
var node2=new SLLNode(5);
var node3=new SLLNode(19);

//assigning head
var head1=node1;
node1.next=node2;
node2.next=node3;
console.log("Has cycle?: "+hasCycle(node1)); //outputs false as expected

Upvotes: 0

Views: 3182

Answers (3)

ujwalka
ujwalka

Reputation: 11

JSON.stringify() can be used to detect cyclic linked lists. CircularDetector returns true if the linked list is cyclic.

function CircularDetector (head) {
  try {
    JSON.stringify(head);
    return false;
  } catch (e) {
    return true;
  }
}

Upvotes: 1

ASHISH R
ASHISH R

Reputation: 4189

Not a very efficient solution as I am using map but if you don't want to use two pointers this solution is easy to understand

// Preparation code:
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function hasCycle(head) {
  let node = head;
  let map={};

  while(node){
      if(map[node.value]){
      //return node or true
         return {"Found":node}
      }  
    else{

      map[node.value] = true;
    }
    node = node.next;
  }

  return "Not found";
}

const nodeA = new Node('A');
const nodeB = nodeA.next = new Node('B');
const nodeC = nodeB.next = new Node('C');
const nodeD = nodeC.next = new Node('D');
const nodeE = nodeD.next = new Node('E');
console.log(hasCycle(nodeA)); // => null
nodeE.next = nodeB;
console.log(hasCycle(nodeA))

Upvotes: 0

swallace
swallace

Reputation: 408

You can read more on cycle detection at https://en.wikipedia.org/wiki/Cycle_detection but the main takeaway is that if you move one pointer twice as fast as another pointer then a loop would be identifiable as the fast pointer will eventually catch up with the other. Here's a possible solution in js.

function hasCycle(head) {
  var slow, fast;

  if(!head || !head.next) return false;

    slow = head;
    fast = head;

    if(head.next === head) return true;

    while(fast.next.next) {

      slow = slow.next;
      fast = fast.next.next;

      if(slow === fast) return true;
    }

  return false;

}

Upvotes: 0

Related Questions