Question

With the following structures defined:

struct monster_struct {

      char *name;

      int commonality;

      int weight;

      struct monster_struct *next;

};

typedef struct monster_struct monster;

typedef struct monster_list {

      monster *head;

}

• Write functions to return the second-most-common monster and the third-lightest monster in the list.
• Don’t worry about headers.
• Don’t worry about which way to resolve ties.
• The list will always have three monsters in it.

Answer 1

The approach we will be using will require us to traverse the list multiple times. It will have a time complexity of O(n), which is better than the time that will be required if we sort the list.

(1) char* SecondMostCommon(monster* head)
{
int mostcommon=0;
int secmostcommon=0;
monster* r = head; // declaring another pointer for traversal
while(r!=NULL) //finding the most common monster
{
if(r->commonality>mostcommon)
mostcommon=r->commonality;

head = head->next
}
char* ans;
r = head;
  
while(r!=NULL) //finding the second-most common monster
{
if(r->commonality>secmostcommon && secmostcommon<mostcommon)
{
secmostcommon = r->commonality;
ans = r->name;
}
}
  
return ans;
}

(2) char* ThirdLightestMonster(monster* head) //function to find third-lightest monster
{
int lightest = INT_MAX;
int seclightest = INT_MAX;
int thirdlightest = INT_MAX;
monster* r =head;
while(r!=NULL) //finding the lightest monster
{
if(r->weight<lightest)
lightest = r->weight;
}
r = head;
while(r!=NULL) //finding the second-lightest monster
{
if(r->weight<seclightest && seclightest>lightest)
seclightest = r->weight;
}
r = head;
char* ans;
  
while(r!=NULL) //finding the third-lightest monster
{
if(r->weight<thirdlightest && thirdlightest>seclightest)
{
thirdlightest = r->weight;
ans = r->name;
}
}
return ans;
}