-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathfinding a strarting node of a loop.txt
52 lines (51 loc) · 1.3 KB
/
finding a strarting node of a loop.txt
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
class Main{
static class Node{
int data;
Node next;
public Node(int data){
this.data=data;
this.next=null;
}
}
Node head;
public void create_loop() {
Node first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
Node fourth = new Node(4);
Node fifth = new Node(5);
Node sixth = new Node(6);
head = first;
first.next=second;
second.next=third;
third.next=fourth;
fourth.next=fifth;
fifth.next=sixth;
sixth.next=third;
}
public Node detect_a_loop(){
Node fastPtr=head;
Node slowPtr=head;
while (fastPtr!=null&&fastPtr.next!=null){
fastPtr=fastPtr.next.next;
slowPtr=slowPtr.next;
if (fastPtr==slowPtr){
return getStartingNodeOfLoop(slowPtr);
}
}
return null;
}
public Node getStartingNodeOfLoop(Node slowPtr) {
Node temp=head;
while (temp!=slowPtr){
temp=temp.next;
slowPtr=slowPtr.next;
}
return temp;
}
public static void main(String[] args){
Main sl=new Main();
sl.create_loop();
System.out.println(sl.detect_a_loop().data);
}
}