Commitf710a07

committed

detect

1 parent7bc5a35 commitf710a07Copy full SHA for f710a07

File tree

+55

-0

lines changed

+55

-0

lines changed

Lines changed: 55 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,55 @@`
	`1`	`+packageAlgorithms.list;`
	`2`	`+`
	`3`	`+importAlgorithms.algorithm.others.ListNode;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * Definition for singly-linked list.`
	`7`	`+ * class ListNode {`
	`8`	`+ * int val;`
	`9`	`+ * ListNode next;`
	`10`	`+ * ListNode(int x) {`
	`11`	`+ * val = x;`
	`12`	`+ * next = null;`
	`13`	`+ * }`
	`14`	`+ * }`
	`15`	`+ */`
	`16`	`+publicclassDetectCycle {`
	`17`	`+publicListNodedetectCycle(ListNodehead) {`
	`18`	`+if (head ==null) {`
	`19`	`+returnnull;`
	`20`	`+ }`
	`21`	`+`
	`22`	`+ListNodes =head;`
	`23`	`+ListNodef =head;`
	`24`	`+`
	`25`	`+ListNodecross =null;`
	`26`	`+`
	`27`	`+while (f !=null &&f.next !=null) {`
	`28`	`+s =s.next;`
	`29`	`+f =f.next.next;`
	`30`	`+`
	`31`	`+if (s ==f) {`
	`32`	`+cross =s;`
	`33`	`+`
	`34`	`+// remember to break here, or you will get a loop.`
	`35`	`+break;`
	`36`	`+ }`
	`37`	`+ }`
	`38`	`+`
	`39`	`+// don't detect any cycle.`
	`40`	`+if (cross ==null) {`
	`41`	`+returnnull;`
	`42`	`+ }`
	`43`	`+`
	`44`	`+// place the slow to the start again.`
	`45`	`+s =head;`
	`46`	`+while (true) {`
	`47`	`+if (s ==f) {`
	`48`	`+returns;`
	`49`	`+ }`
	`50`	`+`
	`51`	`+s =s.next;`
	`52`	`+f =f.next;`
	`53`	`+ }`
	`54`	`+ }`
	`55`	`+}`

Comments

(0)