-
Notifications
You must be signed in to change notification settings - Fork 77
/
MergePoint.java
145 lines (112 loc) · 3.93 KB
/
MergePoint.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
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));
node = node.next;
if (node != null) {
bufferedWriter.write(sep);
}
}
}
// Complete the findMergeNode function below.
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
SinglyLinkedListNode temp1= head1, temp2 = head2;
while(temp1!=null)
{
while(temp2!=null)
{
if(temp1==temp2)
return temp1.data;
temp2 = temp2.next;
}
temp1 = temp1.next;
temp2 = head2;
}
return 1;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int tests = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int testsItr = 0; testsItr < tests; testsItr++) {
int index = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
SinglyLinkedList llist1 = new SinglyLinkedList();
int llist1Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < llist1Count; i++) {
int llist1Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
llist1.insertNode(llist1Item);
}
SinglyLinkedList llist2 = new SinglyLinkedList();
int llist2Count = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < llist2Count; i++) {
int llist2Item = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
llist2.insertNode(llist2Item);
}
SinglyLinkedListNode ptr1 = llist1.head;
SinglyLinkedListNode ptr2 = llist2.head;
for (int i = 0; i < llist1Count; i++) {
if (i < index) {
ptr1 = ptr1.next;
}
}
for (int i = 0; i < llist2Count; i++) {
if (i != llist2Count-1) {
ptr2 = ptr2.next;
}
}
ptr2.next = ptr1;
int result = findMergeNode(llist1.head, llist2.head);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}