I have a class that I need to write a mergeLists method (the method is to merge

Question

I have a class that I need to write a mergeLists method (the method is to merge two lists into a new list) for, I'm not sure how to write it so if someone could write it and explain what they did they would be a Lifesaver! :)

So for example if I had
List1: 2 6 7
List2: 3 5 8

a new list would be created that would be
newList: 2 3 5 6 7 8

and List1 and List2 would be empty

Here is my code:

I need to write a method to clearList method that recovers all memory but I'm not sure how to write it, if someone could write it and explain how they did it you would be a Lifesaver! :)

Here is my class:


public class OrderedLinkedList extends LinkedListClass
{
protected LinkedListNode first; //variable to point to the first node
protected LinkedListNode last; //variable to point to the last node
protected int count; //variable to store the number of nodes
//in the list

//default constructor
public OrderedLinkedList()
{
super();
}

//copy constructor
public OrderedLinkedList(OrderedLinkedList otherList)
{
super(otherList);
}

//Method to determine whether searchItem is in the list
public boolean search(DataElement searchItem)
{
LinkedListNode current; //variable to traverse the list
boolean found;

current = first; //set current to point to the first node in the list

found = false; //set found to false

while(current != null && !found) //search the list
if(current.info.equals(searchItem)) //item is found
found = true;
else
current = current.link; //make the current point to
//the next node
if(found)
found = current.info.equals(searchItem);

return found;
}

public void insertNode(DataElement insertItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
LinkedListNode newNode; //variable to create a node

boolean found;

newNode = new LinkedListNode(); //create the node
newNode.info = insertItem.getCopy(); //store newItem in the node
newNode.link = null; //set the link field of the node to null

if(first == null) //Case 1
{
first = newNode;
count++;
}
else
{
trailCurrent = first;
current = first;
found = false;

while(current != null && !found) //search the list
if(current.info.compareTo(insertItem) >= 0)
found = true;
else
{
trailCurrent = current;
}

if(current == first) //Case 2
{
newNode.link = first;
first = newNode;
count++;
}
else //Case 3
{
trailCurrent.link = newNode;
newNode.link = current;
count++;
}
}
}

public void deleteNode(DataElement deleteItem)
{
LinkedListNode current; //variable to traverse the list
LinkedListNode trailCurrent; //variable just before current
boolean found;

if(first == null) //Case 1; list is empty.
System.err.println("Cannot delete from an empty list.");
else
{
if(first.info.equals(deleteItem)) //Case 2; the first node is the
//node to be deleted
{
first = first.link;
count--;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point to
//the first node
current = first.link; //set current to point to the
//second node

while(current != null && !found)
{
if(current.info.compareTo(deleteItem) >= 0)
found = true;
else
{
trailCurrent = current;
current = current.link;
}
}

if(current == null) //Case 4; the list is not empty, but the
//item to be delete is not in the list
System.out.println("Item to be deleted is "
+ " not in the list.");
else
if(current.info.equals(deleteItem)) //item to be deleted
//is in the list
{
if(first == current) //Case 2
{
first = first.link;
count--;
}
else //Case 3; the item to be deleted is
//somewhere in the list
{
trailCurrent.link = current.link;
count--;
}
}
else //Case 4
System.out.println("Item to be deleted is "
+ " not in the list.");
}
}
}
}

Explanation / Answer

public node merge_sort (node list1) {
if (list1 == null || list1.next == null)
           return list1; // checks for empty or single list
node list2 = split (list1);
list1 = merge_sort (list1);
list2 = merge_sort (list2);
return merge (list1, list2);
} // end merge_sort

public node split (node list1) {
if (list1 == null || list1.next == null) return null;
node list2 = list1.next;
list1.next = list2.next;
list2.next = split (list2.next);
return list2;
} // end split method

public node merge (node list1, node list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.student.id < list2.student.id) {
  list1.next = merge (list1.next, list2);
  return list1;
} // end if
else {
  list2.next = merge (list1, list2.next);
  return list2;
} // end else
} // end merge method

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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