Finding two minimum elements in a linked list

Question

I am trying to work on linked list to enhance my concepts on pointers.

I have successfully created linked list and it also give the minimum two elements but i tried on number of elements to test it.

Suddenly i found that it was not working for the following exmaple:

enter the size of node
4
start entering the number of elements until your size
6
1
7
59
Printing linked list
6-> 1-> 7-> 59-> 

 The two minimumnumbers are  min1 :1   and min2 : 1

My full code to do so is: You can directly switch to function find_two_min()

#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
#include <string.h>

struct node 
{
    int freq;
    struct node * next;
};
typedef struct node node;
node * tree;

//Problem creating area is below (code for finding minimum two elements)
void find_two_min(node**List,node** lmin1,node** lmin2)
{
    node*temp=*List;    
    node*min1,*min2;
    node*var1=*List;
    node* second=(*List)->next;
    if(var1>second)
    {
      min2=var1;
      min1=second;
    }
    else
    {
      min1=var1;
      min2 =second;
    }
    while(temp!=NULL)
    {
        if(temp->freq<min2->freq)
        {
            min1=min2;
            min2=temp;    
        }
        else if(temp->freq<min1->freq)
        {
            min1=temp;
        }    
        temp=temp->next;
    }
    *lmin1=min1; 
    *lmin2=min2;
}

void main() 
{
    int size, data;
    node* min1, *min2;
    int count = 0; //this count flag is to check is it's first node or not inside the do-while loop.
    tree = NULL;
    printf("enter the size of node\n");
    scanf("%d", & size);
    printf("start entering the number of elements until your size\n");
    node * prev;
    do
    {
        scanf("%d", & data);
        if (count == 0)
        {
            node * temp;
            temp = (node * ) malloc(sizeof(node));
            temp-> freq = data;
            temp-> next = NULL;
            prev = temp;
            tree=prev;
        } 
        else
        {
            node * temp ;
            temp = (node * ) malloc(sizeof(node));
            temp-> freq = data;
            temp-> next = NULL;
            prev-> next = temp;
            prev=prev->next;
        }
        size--;
        ++count;
    }
    while (size > 0);

    printf("Printing linked list\n");
    node * temp1;
    temp1 = tree;
    while (temp1!= NULL) 
    {
        printf("%d-> ", temp1-> freq);
        temp1 = temp1-> next;
    }
    node*temp5=tree;
    find_two_min(&temp5,&min1,&min2);
   printf("\n The two minimumnumbers are  min1 :%d   and min2 : %d\n",min1->freq,min2->freq);

}

Could any one please let me know why it is not working on this particular example, whereas it was working on other samples? Could you please help me in correcting it ?

Answer 1

The problem is you arbitrary set at the beginning min1 as the first element and min2 as the 2nd element, and then - you start traversing from the first element (temp).

This makes you read the first 2 elements twice, and if one of them is the minimum - it is also inserted twice, the algorithm 'thinks' you have two elements with the value 1.

The solution to this problem could be following one of the two approaches:

1. Set min1 and min2 to the first elements, after checking which is indeed smaller, and then start traversing only from the 3rd element - avoid re-reading an element you have already read.
2. (better solution) set min1 and min2 as values that are larger than the range of the elements. A good choice will be using INT_MAX - it will ensure your logic is invoked from the first steps of your algorithm.

Answer 2

You're starting temp at the first node, even though you've already considered both it and the second node in your initialization. Try starting it at the third node instead.