MCX1/4
Math
Department
Mr. Gary. Jaye
Danny Jaye, A.P.S.
1998 Question 3 from APCS AB Exam: Part II
Assume that linked lists of integers are implemented using the following declarations.
struct ListNode {
int info;
ListNode * next;
ListNode(int val, ListNode * ptr) // constructor
: info(val), next(ptr) { }
};
Part A
Write function FirstMin, whose header is given below. FirstMin determines the value of the smallest integer in its list parameter and returns a pointer to the first node in the list that contains that value. (If the list is empty, FirstMin returns NULL.)
For example, if L and p are ListNode * variables:
| linked list L | Result of executing p = FirstMin(L) |
|---|---|
| |
|
| |
|
| |
|
Complete function FirstMin below.
ListNode * FirstMin(ListNode * list) {
}
Part B
Write the function RemoveNext, whose header is given below. RemoveNext has one parameter p, a non-NULL pointer to a node of a linked list. RemoveNext removes the node after the one pointed to by p from the list, returning that node to the heap/to free storage. (If the node pointed to by p is the last node on the list, RemoveNext does nothing.)
For example:
| Before the call RemoveNext(p) | After the call RemoveNext(p) |
|---|---|
 |
 |
 |
 |
 |
|
Complete function RemoveNext below. Assume that RemoveNext is called only with values that satisfy its precondition.
void RemoveNext(ListNode * ptr) {
// precondition: ptr != NULL
}
Part C
Write the function RemoveDupMins, whose header is given below. RemoveDupMins determines the value of the smallest integer in its list parameter and removes from the list all nodes containing that value EXCEPT the first such node. (If the list is empty, RemoveDupMins does nothing.)
For example:
| List L before the call RemoveDupMins(L) | List L after the call RemoveDupMins(L) |
|---|---|
 |
 |
 |
|
 |
 |
 |
 |
In writing RemoveDupMins, you may call FirstMin and RemoveNext of parts (a) and (b). Assume that FirstMin and RemoveNext work as specified, regardless of what you wrote in parts (a) and (b).
Complete RemoveDupMins below.
void RemoveDupMins(ListNode * list) {
}