class NodeList { public int item; public NodeList next; public NodeList(int val)
ID: 3531446 • Letter: C
Question
class NodeList {
public int item;
public NodeList next;
public NodeList(int val) {
item = val; //initialize data
}
public void Print() {
System.out.print("{" + item + "}");
}
}//end class NodeList
/**
* Given two sorted linked list, merge the two linked list into one sorted linked list. Duplication allowed.
* @author
*
*/
class LinkedList {
private int length;
private int data;
private NodeList first; // ref to first link on list
private LinkedList last;
private LinkedList next;
//private LinkedList item;
//Constructor
public LinkedList() {
first = null;
}
/**
* add val into correct position. The order in this linkedList is form lowest to highest, such as 1 2 3 4 5
* @param val the value will be add into linked list
*/
public void add(int val){
//make new link
NodeList newLink = new NodeList(val);
if(length ==0){
newLink.next = null;
} else {
newLink.next = first;
}
first = newLink;
length++;
}
public boolean isEmpty() {
return (last == null);
}
/**
* show all element in the list
*/
public String toString(){
String str = "";
NodeList current = first; //start at beginning of list
while(current != null){
current.Print(); //print data
current = current.next;
}
return str;
}
public void selectionSort(){
for(NodeList node1 = first; node1!=null; node1 = node1.next){
//number of iterations
NodeList min = node1;//assumes min node is the node under considerations
//selects the min node
for(NodeList node2 = node1; node2!=null; node2 = node2.next){
if(min.item > node2.item){
min = node2;
}
}
//swaps the min node with the node in its actual position
NodeList temp = new NodeList(node1.item);
node1.item = min.item;
min.item = temp.item;
}
}
/**
* merge two linked list l1 and l2 together in the correct order, from lowest to highest
* @param l1
* @param l2
* @return result
*/
//ANY IDEAS ON HOW I CAN GET THIS METHOD TO WORK
public static LinkedList merge(LinkedList l1, LinkedList l2){
if(l1 == null && l2 == null)
return null;
LinkedList head = new LinkedList();
LinkedList lc1 = l1;
LinkedList lc2 = l2;
LinkedList cursor = head;
while(lc1 != null && lc2 != null){
cursor.next = new LinkedList();
cursor = cursor.next;
cursor.next = null;
if(lc1.data <= lc2.data){
cursor.data = lc1.data;
lc1 = lc1.next;
}else{
cursor.data = lc2.data;
lc2 = lc2.next;
}
}
//Set lc1 to the one of lc1 and lc2 that is not null
if(lc2 != null)lc1 = lc2;
//Copy the rest of list lc2 - if any
while(lc1 != null){
cursor.next = new LinkedList();
cursor = cursor.next;
cursor.next = null;
cursor.data = lc1.data;
lc1 = lc1.next;
}
//Head contains an empty node followed by all the values in l1 and l2
//in sorted order
return head.next;
}
/**
* test function
* @param args
*/
public static void main(String[] args){
LinkedList l1 = new LinkedList();
LinkedList l2 = new LinkedList();
l1.add(8);
l1.add(9);
l1.add(2);
System.out.println("Before after:");
l1.toString();
System.out.println(" List after:");
l1.selectionSort();
System.out.println(l1);
l2.add(4);
l2.add(9);
l2.add(5);
System.out.println("Before after:");
l2.toString();
System.out.println(" List after:");
l2.selectionSort();
System.out.println(l2);
System.out.println("Merged:");
System.out.println(merge(l1, l2));//{2, 4, 5, 8, 9, 9}
}
}
OUTPUT
Before after:
{2}{9}{8}
List after:
{2}{8}{9}
Before after:
{5}{9}{4}
List after:
{4}{5}{9}
Merged:
Explanation / Answer
here is the modifie version of your code and it is working,i just changed few lines in merge method
and add an additional method public NodeList getFirst(); in LinkedList Class.
class NodeList {
public int item;
public NodeList next;
public NodeList(int val) {
item = val; //initialize data
}
public void Print() {
System.out.print("{" + item + "}");
}
}//end class NodeList
/**
* Given two sorted linked list, merge the two linked list into one sorted linked list. Duplication allowed.
* @author
*
*/
public class LinkedList {
private int length;
private int data;
private NodeList first; // ref to first link on list
private LinkedList last;
private LinkedList next;
//private LinkedList item;
//Constructor
public LinkedList() {
first = null;
}
public NodeList getFirst()
{
return first;
}
/**
* add val into correct position. The order in this linkedList is form lowest to highest, such as 1 2 3 4 5
* @param val the value will be add into linked list
*/
public void add(int val){
//make new link
NodeList newLink = new NodeList(val);
if(length ==0){
newLink.next = null;
} else {
newLink.next = first;
}
first = newLink;
length++;
}
public boolean isEmpty() {
return (last == null);
}
/**
* show all element in the list
*/
public String toString(){
String str = "";
NodeList current = first; //start at beginning of list
while(current != null){
current.Print(); //print data
current = current.next;
}
return str;
}
public void selectionSort(){
for(NodeList node1 = first; node1!=null; node1 = node1.next){
//number of iterations
NodeList min = node1;//assumes min node is the node under considerations
//selects the min node
for(NodeList node2 = node1; node2!=null; node2 = node2.next){
if(min.item > node2.item){
min = node2;
}
}
//swaps the min node with the node in its actual position
NodeList temp = new NodeList(node1.item);
node1.item = min.item;
min.item = temp.item;
}
}
/**
* merge two linked list l1 and l2 together in the correct order, from lowest to highest
* @param l1
* @param l2
* @return result
*/
//ANY IDEAS ON HOW I CAN GET THIS METHOD TO WORK
public static LinkedList merge(LinkedList l1, LinkedList l2){
if(l1 == null && l2 == null)
return null;
LinkedList mergeList = new LinkedList();
NodeList lc1=l1.getFirst();
NodeList lc2=l2.getFirst();
while(lc1 != null && lc2 != null){
if(lc1.item <= lc2.item){
if(lc1.item==lc2.item)
{
mergeList.add(lc1.item);
mergeList.add(lc2.item);
lc1=lc1.next;
lc2=lc2.next;
}
else
{
mergeList.add(lc1.item);
lc1=lc1.next;
}
}
else{
mergeList.add(lc2.item);
lc2 = lc2.next;
}
}
//Set lc1 to the one of lc1 and lc2 that is not null
if(lc2 != null)lc1 = lc2;
//Copy the rest of list lc2 - if any
while(lc1 != null){
mergeList.add(lc1.item);
lc1 = lc1.next;
}
//Head contains an empty node followed by all the values in l1 and l2
//in sorted order
return mergeList;
}
/**
* test function
* @param args
*/
public static void main(String[] args){
LinkedList l1 = new LinkedList();
LinkedList l2 = new LinkedList();
l1.add(8);
l1.add(9);
l1.add(2);
System.out.println("Before after:");
l1.toString();
System.out.println(" List after:");
l1.selectionSort();
System.out.println(l1);
l2.add(4);
l2.add(9);
l2.add(5);
System.out.println("Before after:");
l2.toString();
System.out.println(" List after:");
l2.selectionSort();
System.out.println(l2);
System.out.println("Merged:");
System.out.println(merge(l1, l2));//{2, 4, 5, 8, 9, 9}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.