-
Notifications
You must be signed in to change notification settings - Fork 22
/
Detect cycle in LinkedList
120 lines (98 loc) · 3.98 KB
/
Detect cycle in LinkedList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
Algorithm:
Use a slow pointer which would be increased by 1 in each iteration
Use a fast pointer which would be increased by 2 in each iteration
Check whether slow and fast pointer meet each other. If YES, then loop is detected. Otherwise, no loop present
*/
package Amazon;
public class LinkedList<T> {
public static class LinkedListNode<T>
{
private T data;
private LinkedListNode<T> next;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public LinkedListNode<T> getNext() {
return next;
}
public void setNext(LinkedListNode<T> next) {
this.next = next;
}
public LinkedListNode(T data) {
super();
this.data = data;
}
@Override
public String toString() {
return "LinkedListNode [data=" + data + "]";
}
}
private LinkedListNode<T> head = null;
private LinkedListNode<T> tail = null;
public LinkedList()
{
head = null;
}
public synchronized void addToBegin(T data)
{
LinkedListNode<T> newNode = new LinkedListNode<T>(data);
newNode.setNext(head); // Also takes care of head == NULL
head = newNode;
if ( tail == null)
tail = head;
}
public synchronized void addToEnd(T data)
{
LinkedListNode<T> newNode = new LinkedListNode<T>(data);
if ( tail == null) // linkedlist is empty
{
tail = head = newNode;
} else {
tail.setNext(newNode);
tail = newNode;
}
}
@Override
public String toString() {
StringBuilder strBuilder = new StringBuilder();
LinkedListNode<T> itr = head;
while ( (itr != null) && (itr.getNext() != null))
{
strBuilder.append(itr).append("\n");
itr = itr.getNext();
}
if ( itr != null)
strBuilder.append(itr);
return strBuilder.toString();
}
public synchronized void insertCycle()
{
if ( null != tail)
tail.setNext(head);
}
public synchronized boolean isCyclePresent()
{
LinkedListNode<T> slowItr = head;
LinkedListNode<T> fastItr = head;
if ( null == slowItr)
return false; // No cycle in empty linked-list
while ( true)
{
slowItr = slowItr.getNext();
fastItr = fastItr.getNext();
if ( null == fastItr) // Seen the tail and no cycle, return false
return false;
// No need to check for null check for slow as fast
// is ahead and linked-list is expected to be static
fastItr = fastItr.getNext();
if ( null == fastItr)
return false;
else if ( fastItr == slowItr) // reference check alone is enough. No need for equals()
return true;
}
}
}