forked from PrajaktaSathe/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRemoveloopinLinkedList.java
More file actions
150 lines (126 loc) · 3.73 KB
/
RemoveloopinLinkedList.java
File metadata and controls
150 lines (126 loc) · 3.73 KB
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
//Contributed by Dev jr - https://github.com/Dev-jr-8
class Solution
{
//Function to remove a loop in the linked list.
public static void removeLoop(Node head){
// code here
// remove the loop without losing any nodes
//Slow fast Pointers Approach
Node slow = head;
Node fast = head;
while(fast!=null)
{
//moving fast pointer by two nodes and slow pointer by one node
fast = fast.next;
if(fast!=null)
{
fast = fast.next;
slow = slow.next;
}
//if they met, means loop detected
if(fast==slow)
{
//reassinging head to slow
slow = head;
//if cycle is present in head pointer itself
if(fast == slow)//new slow is pointing to head
{
while(fast.next!=slow)fast = fast.next;
}
//else make fast pointer to revolve around the loop
//make slow pointer to make a move each time towards the cycle
//if next of both is same(fast is common for both cases)
//make fast's next as null
else
{
while(fast.next!=slow.next)
{
fast = fast.next;
slow = slow.next;
}
}
fast.next = null;
}
//Time Complexity : o(n)
//Space Complexity : o(1)
}
}
}
//GeeksforGeeks driver Code
import java.util.*;
import java.io.*;
import java.lang.*;
class Node
{
int data;
Node next;
}
class GFG
{
public static Node newNode(int data){
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
public static void makeLoop(Node head, int x){
if (x == 0)
return;
Node curr = head;
Node last = head;
int currentPosition = 1;
while (currentPosition < x)
{
curr = curr.next;
currentPosition++;
}
while (last.next != null)
last = last.next;
last.next = curr;
}
public static boolean detectLoop(Node head){
Node hare = head.next;
Node tortoise = head;
while( hare != tortoise )
{
if(hare==null || hare.next==null) return false;
hare = hare.next.next;
tortoise = tortoise.next;
}
return true;
}
public static int length(Node head){
int ret=0;
while(head!=null)
{
ret += 1;
head = head.next;
}
return ret;
}
public static void main (String[] args){
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t--> 0)
{
int n = sc.nextInt();
int num = sc.nextInt();
Node head = newNode(num);
Node tail = head;
for(int i=0; i<n-1; i++)
{
num = sc.nextInt();
tail.next = newNode(num);
tail = tail.next;
}
int pos = sc.nextInt();
makeLoop(head, pos);
Solution x = new Solution();
x.removeLoop(head);
if( detectLoop(head) || length(head)!=n )
System.out.println("0");
else
System.out.println("1");
}
}
}