I am ashamed to say this, I am stuck this Java Programming Project :( Please hel

Question

I am ashamed to say this, I am stuck this  Java Programming Project :(  Please help!

Thank you a bunch!!
-----------------------------------------------------------------------------------------

Write a method that takes a linked list of integers and rearranges the nodes so that the integers stored are sorted into the order of smallest to largest, with the smallest integer at the head of the list.

Your method should preserve repetition of integers. If the original list had any integers occurring more than once, then the changed list will have the same number of each integer. For concreteness you will use lists of integers, but your method should still work if you replace the integer type with any other type for which the less-than operation is defined.

Use the following specification:

IntNode listSort(IntNode head)
// Postcondition: The return value is a head
// reference of a linked list with exactly the
// same entries as the original list (including
// repetitions if any), but the entries
// in this list are sorted from smallest to
// largest. The original linked list is no longer
// available.

Your method will implement the following algorithm (which is often called selection sort):
The algorithm removes nodes one at a time from the original list and adds the nodes to a second list until all the nodes have been moved to the second list. The second list will then be sorted.


// Pseudocode for selection sort
while (the first list still has some nodes
{
1. Find the node with the largest element of all the nodes in the first list.
2. Remove this node from the first list.
3. Add this node at the head of the second list.
}

Note that your method will move entire nodes, not just elements, to the second list. Thus, the first list will get shorter and shorter until it is an empty list. Your method should not need to use the new operator since it is just moving nodes from one list to another list (not creating new nodes).

Explanation / Answer

intnode listSort(intNode *head, int n) {int i, j;intNode tempPtr;intNode currentPtr; intNode nextPtr; currentPtr = head; nextPtr = currentPtr->next;for( j = 0; j nextPtr->val) { /* it less than ...*/ tempPtr = currentPtr;/* ...swap with temp */ currentPtr = nextPtr; nextPtr = tempPtr;} nextPtr = nextPtr->next;} currentPtr = currentPtr->next; } return currentPtr;}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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