Inserting in a sorted linked list(sorted alphabetically)

[crestaldin]

[COLOR=Navy]Pls I need help on how to insert elements into a sorted linked list.I actually have a list that contains names and scores for students and I want the elements to be inserted into the right postion such that the names of individual students are arranged alphabetically.

This is my code but something seems to be wrong.

***********************************************

#include "iostream"
using namespace std;

struct Node
{
char *name;
int score;
Node *next;
};
Node *head=NULL;

void InsertItem(Node * &head);

void main()
{
InsertItem(head);
}

void InsertItem(Node * &head)
{
Node *temp, *previous,*current; /*previous stores the node before the insertion point*/

temp=new Node();

cout<<"Enter name";
cin>>temp->name;
cout<<"Enter score";
cin>>temp->score;

if (head == NULL) /* first node in the list */
{

head = temp;
}
else if (strcmp(head->name,temp->name)>=0)/* insert at the head */
{

temp->next = head;
head = temp;
}
else
{
previous = head; /* trailing pointer */
current = head->next;

while ((current != NULL) && strcmp(current->name,temp->name)<0)
{
previous = current;
current = current->next;
}
temp->next=previous->next;
previous->next=temp;

}


}

***********************************************

[Clinton Portis]

Here is one method you could use to sort your linked list alphabetically:
(I haven't tested this specific code but the idea is sound)

First, push each node into an array of nodes:

Node **array = new Node*[size];
Node *temp = head_ptr;

while(temp)
{
   Node[i] = temp;
   temp = temp->next;
}

Now sort your array of Nodes based on the first letter of each name:

#include<algorithm>

//This function sorts to ascending order
sort(Node[0]->name[0], Node[size]->name[0]);

Now.. all you have to do is include a provision on what to do if the first 2 letters of a person's name are the same.

Once you are done with all your sorting operations, turn the array of nodes back into a linked list. Make each node of the newly sorted list point to the next node in line by resetting all the *next pointers:

head_ptr = Nodes[0];

for(int i=0; i<size-1; i++)

   Nodes[i]->next = Nodes[i+1];

That's it. You now have a head_ptr that points to beginning of a sorted linked list.

[Nedals]

This assumes that, if the list already exist, it is in 'name' order

...
temp->next = NULL; // add this to temp just after cin

curr = head;
if (curr == NULL) // empty list
{
  head = temp;
}
else
{
  while (curr != NULL)
  {
    if (curr->next == NULL) // end of list
    {
      curr->next = temp;
      break;
    }
    else if (temp->name < curr->name) // insert temp
    {
      temp->next = curr->next;
      curr->next = temp;
      break;
    }
    curr = curr->next;
  }
}