Skip to content

Commit a79ff9a

Browse files
RajSDERajSDE
committed
upload
1 parent 0fbb4e2 commit a79ff9a

4 files changed

Lines changed: 470 additions & 0 deletions

File tree

‎JavaPractice/IntersectionPointinYShappedLinkedLists/Readme.md‎

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,149 @@
1+
## Intersection Point in Y Shapped Linked Lists
2+
Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other. [🔗Goto](https://practice.geeksforgeeks.org/problems/intersection-point-in-y-shapped-linked-lists/1/?page=1&difficulty[]=1&status[]=unsolved&company[]=Amazon&sortBy=submissions#)
3+
4+
Example 1:
5+
>**Input**:
6+
>LinkList1 = 3->6->9->common
7+
>LinkList2 = 10->common
8+
>common = 15->30->NULL
9+
>**Output**: 15
10+
11+
<details>
12+
<summary>Full Code</summary>
13+
14+
```
15+
import java.util.*;
16+
17+
18+
class Node
19+
{
20+
int data;
21+
Node next;
22+
Node(int d) {
23+
data = d;
24+
next = null;
25+
}
26+
}
27+
28+
class LinkedList_Intersection
29+
{
30+
Node head = null;
31+
Node tail = null;
32+
33+
public void addToTheLast(Node node)
34+
{
35+
36+
if (head == null) {
37+
head = node;
38+
tail = head;
39+
} else {
40+
//Node temp = head;
41+
//while (temp.next != null)
42+
//temp = temp.next;
43+
44+
//temp.next = node;
45+
tail.next=node;
46+
tail = node;
47+
}
48+
}
49+
50+
/* Function to print linked list */
51+
void printList()
52+
{
53+
Node temp = head;
54+
while (temp != null)
55+
{
56+
System.out.print(temp.data+" ");
57+
temp = temp.next;
58+
}
59+
System.out.println();
60+
}
61+
62+
63+
64+
/* Driver program to test above functions */
65+
public static void main(String args[])
66+
{
67+
68+
69+
/* Constructed Linked List is 1->2->3->4->5->6->
70+
7->8->8->9->null */
71+
Scanner sc = new Scanner(System.in);
72+
int t=sc.nextInt();
73+
74+
while(t>0)
75+
{
76+
int n1 = sc.nextInt();
77+
int n2 = sc.nextInt();
78+
int n3 = sc.nextInt();
79+
LinkedList_Intersection llist1 = new LinkedList_Intersection();
80+
LinkedList_Intersection llist2 = new LinkedList_Intersection();
81+
LinkedList_Intersection llist3 = new LinkedList_Intersection();
82+
83+
int a1=sc.nextInt();
84+
Node head1= new Node(a1);
85+
Node tail1= head1;
86+
87+
for (int i = 1; i < n1; i++)
88+
{
89+
int a = sc.nextInt();
90+
tail1.next = (new Node(a));
91+
tail1= tail1.next;
92+
}
93+
94+
95+
int b1=sc.nextInt();
96+
Node head2 = new Node(b1);
97+
Node tail2 = head2;
98+
for (int i = 1; i < n2; i++)
99+
{
100+
int b = sc.nextInt();
101+
tail2.next = (new Node(b));
102+
tail2= tail2.next;
103+
}
104+
105+
int c1=sc.nextInt();
106+
Node head3= new Node(c1);
107+
tail1.next = head3;
108+
tail2.next = head3;
109+
Node tail3=head3;
110+
for (int i = 1; i < n3; i++)
111+
{
112+
int c = sc.nextInt();
113+
tail3.next = (new Node(c));
114+
tail3= tail3.next;
115+
}
116+
117+
Intersect obj = new Intersect();
118+
System.out.println(obj.intersectPoint(head1, head2));
119+
t--;
120+
}
121+
}
122+
}
123+
```
124+
</details>
125+
126+
```
127+
class Intersect
128+
{
129+
int intersectPoint(Node head1, Node head2)
130+
{
131+
Node p=head1;
132+
Node q=head2;
133+
Set<Node> a=new HashSet<Node>();
134+
while(p!=null)
135+
{
136+
a.add(p);
137+
p=p.next;
138+
}
139+
while(q!=null)
140+
{
141+
if(a.contains(q))
142+
break;
143+
q=q.next;
144+
}
145+
return q.data;
146+
}
147+
}
148+
149+
```

‎JavaPractice/RemoveloopinLinkedList/Readme.md‎

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
## Remove loop in Linked List
2+
Given a linked list of N nodes such that it may contain a loop.
3+
4+
> A loop here means that the last node of the link list is connected to the node at position X. If the link list does not have any loop, X=0.
5+
6+
Remove the loop from the linked list, if it is present. [🔗Goto](https://practice.geeksforgeeks.org/problems/remove-loop-in-linked-list/1/?page=1&difficulty[]=1&status[]=unsolved&company[]=Amazon&sortBy=submissions#)
7+
8+
<details>
9+
<summary>Full Code</summary>
10+
11+
```
12+
import java.util.*;
13+
import java.io.*;
14+
import java.lang.*;
15+
16+
class Node
17+
{
18+
int data;
19+
Node next;
20+
}
21+
22+
class GFG
23+
{
24+
public static Node newNode(int data){
25+
Node temp = new Node();
26+
temp.data = data;
27+
temp.next = null;
28+
return temp;
29+
}
30+
31+
public static void makeLoop(Node head, int x){
32+
if (x == 0)
33+
return;
34+
Node curr = head;
35+
Node last = head;
36+
37+
int currentPosition = 1;
38+
while (currentPosition < x)
39+
{
40+
curr = curr.next;
41+
currentPosition++;
42+
}
43+
44+
while (last.next != null)
45+
last = last.next;
46+
last.next = curr;
47+
}
48+
49+
public static boolean detectLoop(Node head){
50+
Node hare = head.next;
51+
Node tortoise = head;
52+
while( hare != tortoise )
53+
{
54+
if(hare==null || hare.next==null) return false;
55+
hare = hare.next.next;
56+
tortoise = tortoise.next;
57+
}
58+
return true;
59+
}
60+
61+
public static int length(Node head){
62+
int ret=0;
63+
while(head!=null)
64+
{
65+
ret += 1;
66+
head = head.next;
67+
}
68+
return ret;
69+
}
70+
71+
public static void main (String[] args){
72+
Scanner sc = new Scanner(System.in);
73+
int t = sc.nextInt();
74+
75+
while(t--> 0)
76+
{
77+
int n = sc.nextInt();
78+
79+
int num = sc.nextInt();
80+
Node head = newNode(num);
81+
Node tail = head;
82+
83+
for(int i=0; i<n-1; i++)
84+
{
85+
num = sc.nextInt();
86+
tail.next = newNode(num);
87+
tail = tail.next;
88+
}
89+
90+
int pos = sc.nextInt();
91+
makeLoop(head, pos);
92+
93+
Solution x = new Solution();
94+
x.removeLoop(head);
95+
96+
if( detectLoop(head) || length(head)!=n )
97+
System.out.println("0");
98+
else
99+
System.out.println("1");
100+
}
101+
}
102+
}
103+
```
104+
</details>
105+
106+
```
107+
class Solution
108+
{
109+
public static void removeLoop(Node head){
110+
Node low = head;
111+
Node high = head;
112+
while(low!=null && high != null && high.next != null){
113+
low = low.next;
114+
high = high.next.next;
115+
if(low == high){
116+
break;
117+
}
118+
}
119+
if(low == head){
120+
while(high.next != low){
121+
high = high.next;
122+
}
123+
high.next = null;
124+
}else if(low == high){
125+
low = head;
126+
while(low.next != high.next){
127+
low = low.next;
128+
high = high.next;
129+
}
130+
high.next = null;
131+
}
132+
}
133+
}
134+
```

0 commit comments

Comments
 (0)