-
Notifications
You must be signed in to change notification settings - Fork 34
/
RemoveLoopFromALinkedList.java
220 lines (201 loc) · 5.67 KB
/
RemoveLoopFromALinkedList.java
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
{
import java.util.*;
import java.io.*;
import java.lang.*;
class Node
{
int data;
Node next;
}
class Geeks
{
public static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
public static Node insert(Node head, int data)
{
if (head == null)
head = newNode(data);
else
head.next = insert(head.next, data);
return head;
}
public static void makeLoop(Node head, int x)
{
if (x == 0)
return;
Node curr = head;
Node last = head;
int counter = 0;
while (counter < x)
{
curr = curr.next;
counter++;
}
while (last.next != null)
last = last.next;
last.next = curr;
}
public static int detectloop(Node head)
{
Node hare = head.next;
Node tortoise = head;
while (hare != tortoise && hare != null && tortoise != null)
{
hare = hare.next;
tortoise = tortoise.next;
if (hare != null && hare.next != null)
hare = hare.next;
if (hare == tortoise)
return 1;
}
if (hare == tortoise)
return 1;
return 0;
}
public static int length(Node head, boolean hasloop)
{
int len = 0;
if (hasloop == false)
{
Node temp = head;
while (temp != null)
{
len++;
temp = temp.next;
}
return len;
}
else
{
Node hare = head.next;
Node tortoise = head;
while (hare != tortoise)
{
hare = hare.next;
tortoise = tortoise.next;
hare = hare.next;
if (hare == tortoise)
break;
}
int looplen = 0;
while (hare.next!=tortoise)
{
hare = hare.next;
looplen++;
}
looplen++;
Node begin = head;
int startlen = 0;
tortoise = tortoise.next;
while (begin != tortoise)
{
begin = begin.next;
tortoise = tortoise.next;
startlen++;
}
return looplen + startlen;
}
}
}
class gfg
{
public static void main (String[] args) {
/* code */
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t--> 0)
{
int sizeOfArray = sc.nextInt();
int arr[] = new int[sizeOfArray];
for(int i = 0; i < sizeOfArray; i++)
arr[i] = sc.nextInt();
Node head = null;
for (int i = 0; i < sizeOfArray; i++)
{
head = new Geeks().insert(head, arr[i]);
}
int x = sc.nextInt();
new Geeks().makeLoop(head, x);
int length = 0;
if (new Geeks().detectloop(head) == 1)
{
length=new Geeks().length(head, true);
}
else
{
length = new Geeks().length(head, false);
}
new Loop().removeTheLoop(head);
if (new Geeks().detectloop(head) == 0 && length == new Geeks().length(head, false))
System.out.println("1");
else
System.out.println("0");
}
}
}
}
/*This is a function problem.You only need to complete the function given below*/
/*Complete The function
Node is as follows:
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}*/
class Loop{
// This function will remove the loop from the linked list
public static void removeTheLoop(Node head)
{
Node slow = detectLoop(head);
// System.out.println(slow.data);
if(slow != null)
head_n_remove(slow,head);
}
public static void head_n_remove(Node slow,Node head)
{
Node temp = head;
while(temp != slow)
{
temp = temp.next;
slow = slow.next;
}
// System.out.println("temp" + temp.next.data);
slow = temp.next;
if(slow == temp)
{
slow.next =null;
return;
}
while(slow.next != temp)
{
// System.out.println(slow.data);
slow = slow.next;
}
// System.out.println(slow.data);
slow.next = null;
}
public static Node detectLoop(Node head)
{
Node slow = head, fast = head;
while (slow != null && fast != null && fast.next != null)
{
slow = slow.next;
// System.out.println(slow.data);
fast = fast.next.next;
if(slow == fast)
{
// System.out.println(slow.data);
return slow;
}
}
return null;
}
}