#include <iostream.h>

struct ListNode
{
    int         info;
    ListNode *  next;

    ListNode(int val, ListNode * ptr)   // constructor
	: info(val),
	  next(ptr)
    { }
};

ListNode * FirstMin(ListNode * list)
// postcondition: returns pointer to node with minimal value in list
//                returns pointer to first such node if more than
//                one node contains the minimal value    
{
    ListNode * min = list;

    // list passed by value, so it can be used
    // to traverse instead of using another variable

    while (list != NULL)
    {
	if (list->info < min->info)
	{
	    min = list;
	}
	list = list->next;
    }
    return min;
}

void RemoveNext(ListNode * ptr)
// precondition: ptr != NULL    
{
    ListNode * hold = ptr->next;

    if (hold != NULL)
    {
	ptr->next = hold->next;
	delete hold;
    }
}

void RemoveDupMins(ListNode * list)
// postcondition: all but first minimal nodes removed from list    
{
    ListNode * min = FirstMin(list);

    if (min != NULL)           // there are nodes in the list
    {
        list = min;            // lookahead, so list starts at min

	// invariant: only one node between/including min and list
	// contains min->info
    
	while (list != NULL && list->next != NULL)  // at least two nodes
	{
	    if (list->next->info == min->info)
	    {
		RemoveNext(list);
	    }
	    else
	    {
		list = list->next;	    
	    }
	}	
    }
}

void Print(ListNode * list)
{
    cout << "(";
    while (list != NULL)
    {
	cout << list->info;
	if (list->next != NULL)
	{
	    cout << ", ";
	}
	list = list->next;
    }
    cout << ")" << endl;
}


int main()
{
    ListNode * list1 = new ListNode(3,
			   new ListNode(0,
                               new ListNode(12,
				   new ListNode(0,NULL))));
    

    ListNode * list2 = new ListNode(5,
			   new ListNode(4,
                               new ListNode(5,
				   new ListNode(2,NULL))));

    ListNode * list3 = new ListNode(10,
			   new ListNode(10,
                               new ListNode(10,
				   new ListNode(20,
				       new ListNode(10,NULL)))));
    ListNode * list4 = new ListNode(10,
			   new ListNode(10,NULL));


    Print(list1);
    RemoveDupMins(list1);
    Print(list1);

    Print(list2);
    RemoveDupMins(list2);
    Print(list2);

    Print(list3);
    RemoveDupMins(list3);
    Print(list3);

    Print(list4);
    RemoveDupMins(list4);
    Print(list4);
}