Commit91709ca

applewjg

committed

Linked List Cycle I && II

Change-Id: I66ec88cd863da9ebda61aae1e080a942cf90aff2

1 parent917936e commit91709caCopy full SHA for 91709ca

File tree

+81

-0

lines changed

+81

-0

lines changed

Lines changed: 38 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,38 @@`
	`1`	`+/*`
	`2`	`+ Author: King, higuige@gmail.com`
	`3`	`+ Date: Oct 5, 2014`
	`4`	`+ Problem: Linked List Cycle`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: http://oj.leetcode.com/problems/linked-list-cycle/`
	`7`	`+ Notes:`
	`8`	`+ Given a linked list, determine if it has a cycle in it.`
	`9`	`+ Follow up:`
	`10`	`+ Can you solve it without using extra space?`
	`11`	`+`
	`12`	`+ Solution: two pointers.`
	`13`	`+*/`
	`14`	`+`
	`15`	`+/**`
	`16`	`+ * Definition for singly-linked list.`
	`17`	`+ * class ListNode {`
	`18`	`+ * int val;`
	`19`	`+ * ListNode next;`
	`20`	`+ * ListNode(int x) {`
	`21`	`+ * val = x;`
	`22`	`+ * next = null;`
	`23`	`+ * }`
	`24`	`+ * }`
	`25`	`+ */`
	`26`	`+publicclassSolution {`
	`27`	`+publicbooleanhasCycle(ListNodehead) {`
	`28`	`+if (head ==null \|\|head.next ==null)returnfalse;`
	`29`	`+ListNodeslow =head,fast =head;`
	`30`	`+while (fast !=null &&fast.next !=null) {`
	`31`	`+slow =slow.next;`
	`32`	`+fast =fast.next.next;`
	`33`	`+if (slow ==fast)break;`
	`34`	`+ }`
	`35`	`+if (fast ==null \|\|fast.next ==null)returnfalse;`
	`36`	`+returntrue;`
	`37`	`+ }`
	`38`	`+}`

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Jan 02, 2015`
	`4`	`+ Problem: Linked List Cycle II`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: http://oj.leetcode.com/problems/linked-list-cycle-ii/`
	`7`	`+ Notes:`
	`8`	`+ Given a linked list, return the node where the cycle begins. If there is no cycle, return null.`
	`9`	`+ Follow up:`
	`10`	`+ Can you solve it without using extra space?`
	`11`	`+`
	`12`	`+ Solution: ...`
	`13`	`+*/`
	`14`	`+`
	`15`	`+/**`
	`16`	`+* Definition for singly-linked list.`
	`17`	`+* class ListNode {`
	`18`	`+* int val;`
	`19`	`+* ListNode next;`
	`20`	`+* ListNode(int x) {`
	`21`	`+* val = x;`
	`22`	`+* next = null;`
	`23`	`+* }`
	`24`	`+* }`
	`25`	`+*/`
	`26`	`+publicclassSolution {`
	`27`	`+publicListNodedetectCycle(ListNodehead) {`
	`28`	`+if (head ==null \|\|head.next ==null)returnnull;`
	`29`	`+ListNodeslow =head,fast =head;`
	`30`	`+while (fast !=null &&fast.next !=null) {`
	`31`	`+slow =slow.next;`
	`32`	`+fast =fast.next.next;`
	`33`	`+if (slow ==fast)break;`
	`34`	`+ }`
	`35`	`+if (fast ==null \|\|fast.next ==null)returnnull;`
	`36`	`+slow =head;`
	`37`	`+while (slow !=fast) {`
	`38`	`+slow =slow.next;`
	`39`	`+fast =fast.next;`
	`40`	`+ }`
	`41`	`+returnslow;`
	`42`	`+ }`
	`43`	`+}`

Comments

(0)