Skip to content

Commit 1bf2f86

Browse files
TonnyLTonnyL
committed
feat: 141. Linked List Cycle
1 parent 6a11a73 commit 1bf2f86

14 files changed

Lines changed: 483 additions & 1 deletion

File tree

‎Golang/LinkedListCycle/LinkedListCycle.go‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package LinkedListCycle
2+
3+
//Given a linked list, determine if it has a cycle in it.
4+
//
5+
//Follow up:
6+
//Can you solve it without using extra space?
7+
//
8+
//Waiting to be judged.
9+
10+
type ListNode struct {
11+
Val int
12+
Next *ListNode
13+
}
14+
15+
func hasCycle(head *ListNode) bool {
16+
if head == nil || head.Next == nil {
17+
return false
18+
}
19+
node := head.Next
20+
for ; node != head; {
21+
if node == nil {
22+
return false
23+
}
24+
node = node.Next
25+
}
26+
return true
27+
}
28+
29+
/*func hasCycle(head *ListNode) bool {
30+
slow, fast := head, head
31+
for ; fast != nil && fast.Next != nil; {
32+
slow = slow.Next
33+
fast = fast.Next.Next
34+
if slow == fast {
35+
return true
36+
}
37+
}
38+
return false
39+
}*/

‎Golang/LinkedListCycle/LinkedListCycle_test.go‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package LinkedListCycle
2+
3+
import "testing"
4+
5+
func TestHasCycle(t *testing.T) {
6+
7+
if hasCycle(nil) == false {
8+
t.Log("pass")
9+
} else {
10+
t.Error("failed")
11+
}
12+
13+
if hasCycle(&ListNode{
14+
Val: 0,
15+
}) == false {
16+
t.Log("pass")
17+
} else {
18+
t.Error("failed")
19+
}
20+
21+
node0 := &ListNode{
22+
Val: 0,
23+
Next: &ListNode{
24+
Val: 1,
25+
},
26+
}
27+
node0.Next.Next = node0
28+
if hasCycle(node0) {
29+
t.Log("pass")
30+
} else {
31+
t.Error("failed")
32+
}
33+
34+
if hasCycle(&ListNode{
35+
Val: 0,
36+
Next: &ListNode{
37+
Val: 1,
38+
Next: &ListNode{
39+
Val: 2,
40+
Next: &ListNode{
41+
Val: 0,
42+
},
43+
},
44+
},
45+
}) == false {
46+
t.Log("pass")
47+
} else {
48+
t.Error("failed")
49+
}
50+
51+
}

‎Java/src/LinkedListCycle.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
* Given a linked list, determine if it has a cycle in it.
3+
* <p>
4+
* Follow up:
5+
* Can you solve it without using extra space?
6+
*/
7+
public class LinkedListCycle {
8+
9+
// Time limit exceeded.
10+
/*public boolean hasCycle(ListNode head) {
11+
if (head == null || head.next == null) {
12+
return false;
13+
}
14+
ListNode node = head.next;
15+
while (node != head) {
16+
if (node == null) {
17+
return false;
18+
}
19+
node = node.next;
20+
}
21+
return true;
22+
}*/
23+
24+
// Accepted.
25+
public boolean hasCycle(ListNode head) {
26+
ListNode slow = head, fast = head;
27+
while (fast != null && fast.next != null) {
28+
slow = slow.next;
29+
fast = fast.next.next;
30+
if (slow == fast) {
31+
return true;
32+
}
33+
}
34+
return false;
35+
}
36+
37+
public static class ListNode {
38+
39+
int val;
40+
ListNode next;
41+
42+
ListNode(int x) {
43+
val = x;
44+
next = null;
45+
}
46+
47+
}
48+
49+
}

‎Java/src/LinkedListCycleTest.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
import org.junit.Assert;
2+
import org.junit.Test;
3+
4+
public class LinkedListCycleTest {
5+
6+
@Test
7+
public void testHasCycle() {
8+
LinkedListCycle l = new LinkedListCycle();
9+
10+
Assert.assertFalse(l.hasCycle(null));
11+
12+
Assert.assertFalse(l.hasCycle(new LinkedListCycle.ListNode(0)));
13+
14+
LinkedListCycle.ListNode node0 = new LinkedListCycle.ListNode(0);
15+
node0.next = new LinkedListCycle.ListNode(1);
16+
node0.next.next = node0;
17+
Assert.assertTrue(l.hasCycle(node0));
18+
19+
LinkedListCycle.ListNode node1 = new LinkedListCycle.ListNode(0);
20+
node1.next = new LinkedListCycle.ListNode(1);
21+
node1.next.next = new LinkedListCycle.ListNode(2);
22+
node1.next.next.next = new LinkedListCycle.ListNode(0);
23+
Assert.assertFalse(l.hasCycle(node1));
24+
}
25+
26+
}

‎JavaScript/src/LinkedListCycle.js‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
/**
2+
* Given a linked list, determine if it has a cycle in it.
3+
*
4+
* Follow up:
5+
* Can you solve it without using extra space?
6+
*/
7+
8+
9+
function ListNode(val) {
10+
this.val = val;
11+
this.next = null;
12+
}
13+
14+
/**
15+
* @param {ListNode} head
16+
* @return {boolean}
17+
*/
18+
// Time limit exceeded.
19+
/*let hasCycle = function (head) {
20+
if (head == null || head.next == null) {
21+
return false;
22+
}
23+
let node = head.next;
24+
while (node !== head) {
25+
if (node == null) {
26+
return false;
27+
}
28+
node = node.next;
29+
}
30+
return true;
31+
};*/
32+
33+
// Accepted.
34+
let hasCycle = function (head) {
35+
let slow = head, fast = head;
36+
while (fast != null && fast.next != null) {
37+
slow = slow.next;
38+
fast = fast.next.next;
39+
if (slow === fast) {
40+
return true;
41+
}
42+
}
43+
return false;
44+
};
45+
46+
47+
if (hasCycle(null) === false) {
48+
console.log("pass")
49+
} else {
50+
console.error("failed")
51+
}
52+
53+
if (hasCycle(new ListNode(0)) === false) {
54+
console.log("pass")
55+
} else {
56+
console.error("failed")
57+
}
58+
59+
let node0 = new ListNode(0);
60+
node0.next = new ListNode(1);
61+
node0.next.next = node0;
62+
if (hasCycle(node0)) {
63+
console.log("pass")
64+
} else {
65+
console.error("failed")
66+
}
67+
68+
let node1 = new ListNode(0);
69+
node1.next = new ListNode(1);
70+
node1.next.next = new ListNode(2);
71+
node1.next.next.next = new ListNode(0);
72+
if (hasCycle(node1) === false) {
73+
console.log("pass")
74+
} else {
75+
console.error("failed")
76+
}

‎Kotlin/src/LinkedListCycle.kt‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
* Given a linked list, determine if it has a cycle in it.
3+
*
4+
* Follow up:
5+
* Can you solve it without using extra space?
6+
*/
7+
class LinkedListCycle {
8+
9+
// Waiting to be judged.
10+
fun hasCycle(head: ListNode?): Boolean {
11+
if (head?.next == null) {
12+
return false
13+
}
14+
var node = head.next
15+
while (node != head) {
16+
if (node == null) {
17+
return false
18+
}
19+
node = node.next
20+
}
21+
return true
22+
}
23+
24+
// Waiting to be judged.
25+
/*fun hasCycle(head: ListNode?): Boolean {
26+
var slow = head
27+
var fast = head
28+
while (fast != null && fast.next != null) {
29+
slow = slow?.next
30+
fast = fast.next?.next
31+
if (slow === fast) {
32+
return true
33+
}
34+
}
35+
return false
36+
}*/
37+
38+
data class ListNode(
39+
val `val`: Int,
40+
var next: ListNode? = null
41+
)
42+
43+
}

‎Kotlin/src/LinkedListCycleTest.kt‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
import org.junit.Assert
2+
import org.junit.Test
3+
4+
class LinkedListCycleTest {
5+
6+
@Test
7+
fun testHasCycle() {
8+
val l = LinkedListCycle()
9+
10+
Assert.assertFalse(l.hasCycle(null))
11+
12+
Assert.assertFalse(l.hasCycle(LinkedListCycle.ListNode(0)))
13+
14+
val node0 = LinkedListCycle.ListNode(0).apply {
15+
next = LinkedListCycle.ListNode(1)
16+
}
17+
node0.next?.next = node0
18+
Assert.assertTrue(l.hasCycle(node0))
19+
20+
val node1 = LinkedListCycle.ListNode(0).apply {
21+
next = LinkedListCycle.ListNode(1).apply {
22+
next = LinkedListCycle.ListNode(2).apply {
23+
next = LinkedListCycle.ListNode(0)
24+
}
25+
}
26+
}
27+
Assert.assertFalse(l.hasCycle(node1))
28+
}
29+
30+
}

‎Python/LinkedListCycle.py‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
# Given a linked list, determine if it has a cycle in it.
2+
#
3+
# Follow up:
4+
# Can you solve it without using extra space?
5+
#
6+
#
7+
8+
9+
class LinkedListCycle:
10+
11+
# Time limit exceed.
12+
# def hasCycle(self, head):
13+
# """
14+
# :type head: ListNode
15+
# :rtype: bool
16+
# """
17+
# if head is None or head.next is None:
18+
# return False
19+
# node = head.next
20+
# while node != head:
21+
# if node is None:
22+
# return False
23+
# node = node.next
24+
#
25+
# return True
26+
27+
# Accepted.
28+
def hasCycle(self, head):
29+
slow, fast = head, head
30+
while fast is not None and fast.next is not None:
31+
slow = slow.next
32+
fast = fast.next.next
33+
if slow == fast:
34+
return True
35+
36+
return False
37+
38+
39+
class ListNode:
40+
def __init__(self, x):
41+
self.val = x
42+
self.next = None

‎Python/LinkedListCycleTest.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
from unittest import TestCase
2+
3+
from LinkedListCycle import LinkedListCycle, ListNode
4+
5+
6+
class TestLinkedListCycle(TestCase):
7+
def test_hasCycle(self):
8+
llc = LinkedListCycle()
9+
10+
self.assertFalse(llc.hasCycle(None))
11+
12+
node0 = ListNode(0)
13+
node0.next = ListNode(1)
14+
node0.next.next = node0
15+
self.assertTrue(llc.hasCycle(node0))
16+
17+
node1 = ListNode(0)
18+
node1.next = ListNode(1)
19+
node1.next.next = ListNode(2)
20+
node1.next.next.next = ListNode(0)
21+
self.assertFalse(llc.hasCycle(node1))

0 commit comments

Comments
 (0)