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.

Interview Question

Suppose you have two linked lists that merge at some node. The lists could be billions of nodes long. Find the node where the lists merge in the most optimal time while using a low amount of

memory.

Code:

Main

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

LinkedList.java

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 } }

Node.java

package assignment7;

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