The goal in this assignment is to exercise Linked List implementation in Java. Y

Question

The goal in this assignment is to exercise Linked List implementation in Java. You are going to implement insert, remove, count and print functionalities of a linkedList. The linked list will be sorted in the ascending order. You are also going to solve the interview question we discussed in class in a very memory efficient way.

In this problem, you have 2 linkedLists, and these 2 linkedLists merge at a random node. It may be the 100th node in the first linkedList, and the 4th node in the second linked list. It is completely random as shown below.

The goal is to compute this mergeNode in a memory point of view. That is, you could not use extra memory to solve the problem.

I added a template project, and commented 6 functions for you to implement. Node class print method, LinkedList class insert, remove, count and print methods and the testDriver class computeTheMergeNode method. Use the main method as it is. Do not update the main method I provided.

package assignment7;

import java.util.Random;

public class Assignment_7 {

public static Node computeTheMergeNode(LinkedList lst1, LinkedList lst2){
  
// Implement this function
return (null);
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
  
Random random = new Random();
  
int szList1UntilMerge = random.nextInt(100);
int szList2UntilMerge = random.nextInt(100);
int szListAfterMerge = random.nextInt(100);
  
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
  
for (int i=0;i<szList1UntilMerge;i++){
int value = random.nextInt(1000);
list1.insert(value);
}
  
if (list1.count() != szList1UntilMerge){
System.out.print("There is an error in the insert function!");
}
  
list1.remove(list1.mHead.mValue);
  
if (list1.count() != szList1UntilMerge-1){
System.out.print("There is an error in the remove function!");
}
  
Node mergeNode = list1.insert(2000+random.nextInt(100));
  
if (list1.count() != szList1UntilMerge){
System.out.print("There is an error in the insert function!");
}
  
for (int i=0;i<szListAfterMerge;i++){
int value = mergeNode.mValue + 1 + random.nextInt(1000);
list1.insert(value);
}
  
if (list1.count() != szList1UntilMerge+szListAfterMerge){
System.out.print("There is an error in the insert function!");
}
  
for (int i=0;i<szList2UntilMerge;i++){
int value = random.nextInt(1000);
list2.insert(value);
}
  
if (list2.count() != szList2UntilMerge){
System.out.print("There is an error in the insert function!");
}
  
list2.remove(list2.mHead.mValue);
  
if (list2.count() != szList2UntilMerge-1){
System.out.print("There is an error in the remove function!");
}
  
Node curr = list2.mHead;
Node prev = null;
while (curr != null){
prev = curr;
curr = curr.mNext;
}
  
prev.mNext = mergeNode;
  
if (list2.count() != szList2UntilMerge+szListAfterMerge){
System.out.print("There is an error in the merge function!");
}
  
System.out.println("List 1:");
list1.print();
System.out.println("List 2:");
list2.print();
  
Node mergeNode2 = computeTheMergeNode(list1, list2);
  
if (mergeNode == mergeNode2){
System.out.println("MergeNode correctly detected");
System.out.println(mergeNode2.mValue);
}
else{
System.out.println("Please check your algorithm!");
}
}
  
}

package assignment7;

public class LinkedList {
Node mHead;
  
public LinkedList(){
mHead = null;
}
  
public Node insert(int value){
  
// Implement this function
return null;
}
  
  
public void remove(int value){
  
// Implement this function
}
  
public int count(){
  
// Implement this function
return (0);
}
  
public void print(){
// Implement this function
// Ensure that you call Node's print method
}
  
}

package assignment7;

public class Node {
int mValue;
Node mNext;
  
public Node(int value){
mValue = value;
}
  
public void print(){
// Implement this function
}
  
}

Explanation / Answer

Hi Dear,

Please find my implementation.

Please let me know in case of any issue.

Output:

List 1:
127
161
163
176
191
200
203
203
207
210
223
242
247
253
276
297
302
307
308
309
310
347
355
362
367
376
399
401
411
433
434
437
456
472
477
495
502
512
517
545
561
573
573
585
617
619
621
623
628
629
650
657
662
664
678
687
687
696
734
738
741
754
755
755
756
760
772
775
779
789
797
817
835
848
856
859
860
860
864
874
900
916
923
937
951
957
966
974
1001
1033
1035
1087
1090
1104
2039
List 2:
51
116
127
200
383
383
436
480
487
912
977
988
127
161
163
176
191
200
203
203
207
210
223
242
247
253
276
297
302
307
308
309
310
347
355
362
367
376
399
401
411
433
434
437
456
472
477
495
502
512
517
545
561
573
573
585
617
619
621
623
628
629
650
657
662
664
678
687
687
696
734
738
741
754
755
755
756
760
772
775
779
789
797
817
835
848
856
859
860
860
864
874
900
916
923
937
951
957
966
974
1001
1033
1035
1087
1090
1104
2039
MergeNode correctly detected
127

Please DONT forgot to rate my answer. We are working hard for you Guys!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.