forked from joharbatta/DataStructure-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathremoveLoop.java
More file actions
171 lines (138 loc) · 4.06 KB
/
Copy pathremoveLoop.java
File metadata and controls
171 lines (138 loc) · 4.06 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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
import java.util.Scanner;
class removeLoop {
static Node headNode;
/* Structure of the node of linked list */
static class Node {
/* data of the node*/
int data;
/* This is used to point the next node of
the currNode node */
Node next;
Node(int value) {
data = value;
next = null;
}
}
/* This method does the following:
1. If there is a loop in the linked list, it should print 'Yes'
and remove the loop in the linked list and return the head node.
2. If there is no loop in the linked list, it should print 'No'
and return the head node of the linked list. */
Node removeloop(Node head)
{
Node fastNode=head;
Node slowNode=head;
boolean isLoopExists=false;
// floyad's warshell cycle
while(slowNode!=null && fastNode!=null && fastNode.next!=null)
{
fastNode=fastNode.next.next;
slowNode=slowNode.next;
if(fastNode==slowNode)
{
isLoopExists=true;
}
}
if(isLoopExists)
{
slowNode=head;
Node previous=null;
while(slowNode!=fastNode)
{
previous=fastNode;
fastNode=fastNode.next;
slowNode=slowNode.next;
}
System.out.println("YES");
previous.next=null;
return head;
}
else
{
System.out.println("NO");
return head;
}
}
/* This method adds a new node with data 'newData' to
the front of the linked list*/
public void addAtHead(int newData) {
/* Create a new Node of data newData */
Node newNode = new Node(newData);
/* Now, set the next of the newNode as headNode */
newNode.next = headNode;
/* Next, make this newNode as head*/
headNode = newNode;
}
/* This method prints every node of the linked list from the head,
separating by a space */
void printLinkedList(Node head) {
Node tempNode = head;
while (tempNode != null) {
System.out.print(tempNode.data + " ");
tempNode = tempNode.next;
}
}
// Driver program to test above functions
public static void main(String[] args) {
removeLoop list = new removeLoop();
Scanner in = new Scanner(System.in);
/* Get the number of nodes of the linked list from input */
int n = in.nextInt();
/* Get all nodes of the linked list from input */
for (int i = 0; i < n; i++)
{
list.addAtHead(in.nextInt());
}
/* Get the value of k from input */
int k = in.nextInt();
/* Creating a loop, by making the next node of the last node
as the kth node from the head of the linked list */
if (k != 0) {
Node first = headNode, last;
for (int i = 0; i < k; i++) {
first = first.next;
}
last = first;
while (last.next != null) {
last = last.next;
}
last.next = first;
}
/* Print the linked list after removing the loop */
list.printLinkedList(list.removeloop(headNode));
}
}
// public class removeLoop
// {
// public void rmloop(Node head)
// {
// Node fastNode=head;
// Node slowNode=head;
// boolean isLoopExists=false;
// // floyad's warshell cycle
// while(slowNode!=null && fastNode!=null && fastNode.next!=null)
// {
// fastNode=fastNode.next.next;
// slowNode=slowNode.next;
// if(fastNode==slowNode)
// {
// isLoopExists=true;
// }
// }
// if(isLoopExists)
// {
// slowNode=head;
// Node previous=null;
// while(slowNode!=fastNode)
// {
// previous=fastNode;
// fastNode=fastNode.next;
// slowNode=slowNode.next;
// }
// System.out.println("loop node found"+slowNode.data);
// previous.next=null;
// }
// }
// public static void main(String[] args) {
// }
// }