Sorting linked list by int values

[smallrubberfeet]

Hello, I need to sort the following by ID as I enter them into a linked list by while loop. So far I can build through the list, but I'm not sure how to sort by ID as they are entered:

Albert 1000 55.5 150
Babs 3000 60 110
Freida 1150 71 175.5
Big_Al 2000 77 244
Tiny 1550 44 77

nodeType *first, *newNode, *last;
    
    first = NULL;
    last = NULL;
    
    while (inFile)
    {
        newNode = new nodeType; //01x
        inFile >> newNode->info.firstname;
        inFile >> newNode->info.id;
        inFile >> newNode->info.height;
        inFile >> newNode->info.weight;
        newNode->link = NULL;
        
        if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            last->link = newNode;
            last = newNode;
        }
        
}

Thanks for the help!

[mazzica1]

i think you need this

if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            if(first->info.id>newNode->info.id)
            {
                newNode->link = first;
                first= newNode;
            }
            else
            {
                nodeType *temp=first;
                while(temp!=null && temp->link!=null)
                {
                    if(temp->link->info.id>newNode->info.id)
                    {
                        newNode->link=temp->link;
                        temp->link=newNode;
                        break;
                    }
                    temp=temp->link;
                }
                if(temp==null)
                {
                    last->link = newNode;
                    last = newNode;
                }
            }
        }

[smallrubberfeet]

i think you need this

if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            if(first->info.id>newNode->info.id)
            {
                newNode->link = first;
                first= newNode;
            }
            else
            {
                nodeType *temp=first;
                while(temp!=null && temp->link!=null)
                {
                    if(temp->link->info.id>newNode->info.id)
                    {
                        newNode->link=temp->link;
                        temp->link=newNode;
                        break;
                    }
                    temp=temp->link;
                }
                if(temp==null)
                {
                    last->link = newNode;
                    last = newNode;
                }
            }
        }

Exactly the solution I've been trying to think through! Thanks! I ended up drawing it out and came upon this:

if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            if (newNode->info.id > first->info.id)
            {
                last->link = newNode;
                last = newNode;
                newNode->link = first;
                first->link = last;
            }
            last->link = newNode;
            last = newNode;
        }

but I've yet to test it to see if it's sound; basically looked at the new node id, hooked "last" onto it, shot its link (if larger) to the one before, and hooked first up to the front of the that just shot its link. Does this look like a method that would work?

[smallrubberfeet]

i think you need this

if (first == NULL) //first case init
        {
            first = newNode;
            last = newNode;
        }
        else
        {
            if(first->info.id>newNode->info.id)
            {
                newNode->link = first;
                first= newNode;
            }
            else
            {
                nodeType *temp=first;
                while(temp!=null && temp->link!=null)
                {
                    if(temp->link->info.id>newNode->info.id)
                    {
                        newNode->link=temp->link;
                        temp->link=newNode;
                        break;
                    }
                    temp=temp->link;
                }
                if(temp==null)
                {
                    last->link = newNode;
                    last = newNode;
                }
            }
        }

When I run through the list with:

//traverse the linked list
    nodeType *current = first;
    while (current != NULL)
    {
        cout << current->info.firstname << " " << current->info.id;
        cout << endl;
        current = current->link;
    }

It's giving me:

0
Albert 1000

and going to NULL apparently. I've been trying to think through what the problem is, any suggestions?
I'm using your code from above.

[mazzica1]

yes replace

if(temp==NULL)
{
      last->next = newNode;
      last = newNode;
}

with

if(temp==NULL || temp->next==NULL)
{
      last->next = newNode;
      last = newNode;
}