Commitcf0593f

authored

Refactor Cycledetection.js and added it's test. (TheAlgorithms#1099)

1 parentd115214 commitcf0593fCopy full SHA for cf0593f

File tree

+39

-16

lines changed

+39

-16

lines changed

Lines changed: 8 additions & 16 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,32 +1,24 @@`
`1`	`1`	`/**`
`2`		`- * A LinkedList based solution forDetect a Cycle in a list`
	`2`	`+ * A LinkedList based solution forDetecting a Cycle in a list.`
`3`	`3`	`* https://en.wikipedia.org/wiki/Cycle_detection`
`4`	`4`	`*/`
`5`	`5`
`6`		`-functionmain(){`
	`6`	`+functiondetectCycle(head){`
`7`	`7`	`/*`
`8`	`8`	`Problem Statement:`
`9`	`9`	`Given head, the head of a linked list, determine if the linked list has a cycle in it.`
`10`		`-`
`11`		`- Note:`
`12`		`- * While Solving the problem in given link below, don't use main() function.`
`13`		`- * Just use only the code inside main() function.`
`14`		`- * The purpose of using main() function here is to avoid global variables.`
`15`		`-`
`16`	`10`	`Link for the Problem: https://leetcode.com/problems/linked-list-cycle/`
`17`	`11`	`*/`
`18`		`-consthead=''// Reference to head is given in the problem. So please ignore this line`
`19`		`-letfast=head`
`20`		`-letslow=head`
	`12`	`+if(!head){returnfalse}`
`21`	`13`
`22`		`-while(fast!=null&&fast.next!=null&&slow!=null){`
	`14`	`+letslow=head`
	`15`	`+letfast=head.next`
	`16`	`+while(fast&&fast.next){`
	`17`	`+if(fast===slow){returntrue}`
`23`	`18`	`fast=fast.next.next`
`24`	`19`	`slow=slow.next`
`25`		`-if(fast===slow){`
`26`		`-returntrue`
`27`		`-}`
`28`	`20`	`}`
`29`	`21`	`returnfalse`
`30`	`22`	`}`
`31`	`23`
`32`		`-main()`
	`24`	`+export{detectCycle}`

Lines changed: 31 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,31 @@`
	`1`	`+import{detectCycle}from'../CycleDetection'`
	`2`	`+import{Node}from'../SinglyLinkedList'`
	`3`	`+`
	`4`	`+describe('Detect Cycle',()=>{`
	`5`	`+it('should detect loop and return true',()=>{`
	`6`	`+// Creating list and making a loop`
	`7`	`+constheadNode=newNode(10)`
	`8`	`+headNode.next=newNode(20)`
	`9`	`+headNode.next.next=newNode(30)`
	`10`	`+headNode.next.next.next=newNode(40)`
	`11`	`+headNode.next.next.next.next=headNode`
	`12`	`+expect(detectCycle(headNode)).toEqual(true)`
	`13`	`+})`
	`14`	`+`
	`15`	`+it('should not detect a loop and return false',()=>{`
	`16`	`+// Case 0: When head is null, there is no loop.`
	`17`	`+expect(detectCycle(null)).toEqual(false)`
	`18`	`+constheadNode=newNode(10)`
	`19`	`+`
	`20`	`+// Case 1: List with single node doesn't have any loop`
	`21`	`+expect(detectCycle(headNode)).toEqual(false)`
	`22`	`+`
	`23`	`+headNode.next=newNode(20)`
	`24`	`+headNode.next.next=newNode(30)`
	`25`	`+headNode.next.next.next=newNode(40)`
	`26`	`+headNode.next.next.next.next=newNode(50)`
	`27`	`+`
	`28`	`+// Case 2: List not having any loops`
	`29`	`+expect(detectCycle(headNode)).toEqual(false)`
	`30`	`+})`
	`31`	`+})`

Comments

(0)