class NodeList { public int item; public NodeList next; public NodeList( int val
ID: 3531785 • Letter: C
Question
class
NodeList {
public int item;
public NodeList next;
public NodeList(int val) {
item = val; //initialize data
}
public NodeList(){
}
public void printNode() {
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 NodeList first; // ref to first link on list
private NodeList last;
//Constructor
public LinkedList() {
first = null;
}
public boolean isEmpty() {
return (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);
newLink.
next = first;
first = newLink;
newLink.
next = last;
last = newLink;
}
public void append(NodeList result) {
first = result;
}
/**
* show all element in the list
*/
public String toString(){
String str =
"";
NodeList current =
first; //start at beginning of list
while(current != null){
current.printNode();
//print data
current = current.
next;
}
return str;
}
public NodeList getFirst(){
return first;
}
public NodeList MergeSort(NodeList headOriginal) {
if (headOriginal == null || headOriginal.next == null)
return headOriginal;
NodeList a = headOriginal;
NodeList b = headOriginal.
next;
while ((b != null) && (b.next != null)) {
headOriginal = headOriginal.
next;
b = (b.
next).next;
}
b = headOriginal.
next;
headOriginal.
next = null;
return merge(MergeSort(a), MergeSort(b));
}
public static NodeList merge(NodeList l1, NodeList l2) {
NodeList temp =
new NodeList();
NodeList head = temp;
NodeList c = head;
while ((l1 != null) && (l2 != null)) {
if (l1.item <= l2.item)
{
c.
next = l1;
c = l1;
l1 = l1.
next;
}
else {
c.
next = l2;
c = l2;
l2 = l2.
next;
}
}
c.
next = (l1 == null) ? l2 : l1;
return head.next;
}
/*public static NodeList merge(NodeList l1, NodeList l2){
//store head to be returned (the smallest)
NodeList masterHead = l1.item > l2.item? l2 : l1;
//put smaller elements at the beginning
while(l1 != null && l2.next != null && l1.item > l2.item)
{
NodeList nextInList2 = l2.next;
l2.next = l1;
l1 = l2;
l2 = nextInList2;
}
//merging loop
while(l1.next != null && l2 != null){
if(l1.next.item > l2.item)
{
//insert node(s) into the array
NodeList higherNode = l1.next;
l1.next = l2;
//advance until every node being inserted is less that the next
while(l2.next != null && higherNode.item > l2.next.item){
l2 = l2.next;
}
//point back into the list
NodeList nextInList2 = l2.next;
l2.next = higherNode;
l2= nextInList2;
}
l1 = l1.next;
}
if(l1.next == null)
l1.next = l2;
return masterHead;
}
*/
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(lc2.
item);
lc2=lc2.
next;
}
?
}
else{
?
mergeList.add(lc1.
item);
lc1 = lc1.
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;
}
public static void main(String[] args){
LinkedList l1 =
new LinkedList();
LinkedList l2 =
new LinkedList();
l1.add(8);
l1.add(9);
l1.add(2);
l1.add(2);
l1.add(10);
l1.add(5);
System.
out.println(" Before:");
l1.toString();
System.
out.println(" List after:");
l1.append(l1.MergeSort(l1.getFirst()));
l1.toString();
l2.add(4);
l2.add(9);
l2.add(5);
l2.add(2);
l2.add(9);
System.
out.println(" Before:");
l2.toString();
System.
out.println(" List after:");
l2.append(l2.MergeSort(l2.getFirst()));
l2.toString();
System.
out.println(" Merged:");
System.
out.println(merge(l2,l1));
}
}
THIS IS MY OUTPUT
Before:
{5}{10}{2}{2}{9}{8}
List after:
{2}{2}{5}{8}{9}{10}--sorted from least to greatest
Before:
{9}{2}{5}{9}{4}
List after:
{2}{4}{5}{9}{9}--sorted from least to greatest
Merged:
{10}{9}{8}{5}{2}{9}{9}{5}{4}{2}{2} ---I need to sort this from LEAST to greatest
Explanation / Answer
Node MergeLists(Node list1, Node list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } Node head; if (list1.dataRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.