This is a very popular interview question, which most people go wrong. The ideal solution to this problem is to keep the linked list sorted as you build it. Another question on this website teaches you how to insert elements into a linked list in the sorted order. This really saves a lot of time which would have been required to sort it.
However, you need to Get That Job....
Method1 (Usual method)
The general idea is to decide upon a sorting algorithm (say bubble sort). Then, one needs to come up with different scenarios to swap two nodes in the linked list when they are not in the required order. The different scenarios would be something like
1. When the nodes being compared are not adjacent and one of them is the first node.
2. When the nodes being compared are not adjacent and none of them is the first node
3. When the nodes being compared are adjacent and one of them is the first node.
4. When the nodes being compared are adjacent and none of them is the first node.
One example bubble sort for a linked list goes like this (working C code!)....
#include<stdio.h>
#include<ctype.h>
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int *count, int value);
void print_list(char *listName, struct node *head);
mynode *bubbleSort(mynode *head, int count);
int main()
{
mynode *head;
int count = 0;
head = (struct node *)NULL;
add_node(&head, &count, 100);
add_node(&head, &count, 3);
add_node(&head, &count, 90);
add_node(&head, &count, 7);
add_node(&head, &count, 9);
print_list("myList(BEFORE)", head);
head = bubbleSort(head, count);
print_list("myList(AFTER) ", head);
getch();
return(0);
}
mynode *bubbleSort(mynode *head, int count)
{
int i, j;
mynode *p0, *p1, *p2, *p3;
    for(i = 1; i < count; i++)
{
    p0 = (struct node *)NULL;
    p1 = head;
    p2 = head->next;
    p3 = p2->next;
       for(j = 1; j <= (count - i); j++)
    {
       if(p1->value > p2->value)    
       {
           // Adjust the pointers...       
           p1->next = p3;
           p2->next = p1;
           if(p0)p0->next=p2;
                     // Set the head pointer if it was changed...
           if(head == p1)head=p2;
           // Progress the pointers
           p0 = p2;
           p2 = p1->next;
           p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
       }
       else
       {
          // Nothing to swap, just progress the pointers...
          p0 = p1;
          p1 = p2;
          p2 = p3;
          p3 = p3->next!=(struct node *)NULL?p3->next: (struct node *)NULL;
       }
    }
}
return(head);
}
void add_node(struct node **head, int *count, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;
if(*head == NULL)
{
     *head=temp;
     temp->value=value;
}
else
{
   for(cur=*head;cur->next!=NULL;cur=cur->next);
   cur->next=temp;
   temp->prev=cur;
   temp->value=value;
}
*count = *count + 1;
}
void print_list(char *listName, struct node *head)
{
mynode *temp;
printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
    printf("[%d]->",temp->value);
}
printf("NULL\n");
}
As you can see, the code becomes quite messy because of the pointer logic. Thats why I have not elaborated too much on the code, nor on variations such as sorting a doubly linked list. You have to do it yourself once to understand it.
Method2 (Divide and Conquer using Merge Sort)
Here is some cool working C code...
#include<stdio.h>
#include<ctype.h>
typedef struct node
{
int value;
struct node *next;
struct node *prev;
}mynode ;
void add_node(struct node **head, int value);
void print_list(char *listName, struct node *head);
void mergeSort(struct node** headRef);
struct node *merge2SortedLLs(struct node *head1, struct node *head2);
void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef);
// The main function..
int main()
{
   mynode *head;
   head = (struct node *)NULL;
   add_node(&head, 1);
   add_node(&head, 10);
   add_node(&head, 5);
   add_node(&head, 70);
   add_node(&head, 9);
   add_node(&head, -99);
   add_node(&head, 0);
   print_list("myList", head);
   mergeSort(&head);
   print_list("myList", head);
   getch();
   return(0);
}
// This is a recursive mergeSort function...
void mergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;
// Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL))
{
    return;
}
    // Split head into 'a' and 'b' sublists
splitLLInto2(head, &a, &b);
// Recursively sort the sublists
mergeSort(&a);
mergeSort(&b);
// Merge the two sorted lists together
*headRef = merge2SortedLLs(a, b);
}
// This is an iterative function that joins two already sorted
// Linked lists...
struct node *merge2SortedLLs(struct node *head1, struct node *head2)
{
   struct node *a, *b, *c, *newHead, *temp;
     
   a = head1;
   b = head2;
   c       = (struct node *)NULL;
   newHead = (struct node*)NULL;
       if(a==NULL)return(b);
   else if(b==NULL)return(a);
   while(a!=NULL && b!=NULL)
   {
     if(a->value < b->value)
     {
       //printf("\na->value < b->value\n");
       if(c==NULL)
       {
        c = a;
       }
       else
       {
        c->next = a;
        c = c->next;
       }
       a = a->next;      
     }
     else if(a->value > b->value)
     {
       //printf("\na->value > b->value\n");
       if(c==NULL)
       {
        c = b;
       }
       else
       {
        c->next = b;
        c = c->next;
       }
       b = b->next;
     }
     else
     {
       // Both are equal.
       // Arbitraritly chose to add one of them and make
       // sure you skip both!

       if(c == NULL)
       {
        c = a;
       }
       else
       {
        c->next = a;
        c = c->next;
       }
       
       a = a->next;
       b = b->next;
     }
       
     // Make sure the new head is set...
     if(newHead == NULL)
      newHead = c;
     
   }
     
   if(a==NULL && b==NULL)
     return(newHead);
       
   if(a==NULL)
     c->next = b;
   else if(b==NULL)
     c->next = a;
       
   return(newHead);
    
}
// Uses the fast/slow pointer strategy
//
// This efficient code splits a linked list into two using
// the same technique as the one used to find the
// middle of a linked list!

void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef)
{
struct node* fast;
struct node* slow;
    
if (source==NULL || source->next==NULL)
{
    // length < 2 cases
    *frontRef = source;
    *backRef = NULL;
}
else
{
    slow = source;
    fast = source->next;
    // Advance 'fast' two nodes, and advance 'slow' one node
    while (fast != NULL)
    {
       fast = fast->next;
       if (fast != NULL)
       {
          slow = slow->next;
          fast = fast->next;
       }
    }
    // 'slow' is before the midpoint in the list, so split it in two
    // at that point.
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}
}
void add_node(struct node **head, int value)
{
mynode *temp, *cur;
temp = (mynode *)malloc(sizeof(mynode));
temp->next=NULL;
temp->prev=NULL;

if(*head == NULL)
{
     *head=temp;
     temp->value=value;
}
else
{
   for(cur=*head;cur->next!=NULL;cur=cur->next);
   cur->next=temp;
   temp->prev=cur;
   temp->value=value;
}
}
void print_list(char *listName, struct node *head)
{
mynode *temp;

printf("\n[%s] -> ", listName);
for(temp=head;temp!=NULL;temp=temp->next)
{
    printf("[%d]->",temp->value);
}
    printf("NULL\n");
}
The code to merge two already sorted sub-linked lists into a sorted linked list could be either iterative or recursive. You already saw the iterative version above. Here is a recursive version of the same...
Recursive solution to merge two already sorted linked lists into a single linked list
struct node* sortedMergeRecursive(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
     result = a;
     result->next = sortedMergeRecursive(a->next, b);
}
else
{
     result = b;
     result->next = sortedMergeRecursive(a, b->next);
}
return(result);
}
Also, see how the splitLLInto2() function uses the same technique used to find the middle of a linked list to split a linked list into two without having to keep a count of the number of nodes in the linkes list!
Here is another solution (not that great, though) to split a linked list into two. It used the count of the number of nodes to decide where to split
void splitLLInto2(struct node* source,struct node** frontRef, struct node** backRef)
{
int len = Length(source); //Get the length of the original LL..
int i;
struct node* current = source;
    
if (len < 2)
{
    *frontRef = source;
    *backRef = NULL;
}
else
{
     int hopCount = (len-1)/2;

     for (i = 0; i<hopCount; i++)
     {
        current = current->next;
     }
       
     // Now cut at current
    *frontRef = source;
    *backRef = current->next;
    current->next = NULL;
}
}
Using recursive stack space proportional to the length of a list is not recommended. However, the recursion in this case is ok ? it uses stack space which is proportional to the log of the length of the list. For a 1000 node list, the recursion will only go about 10 deep. For a 2000 node list, it will go 11 deep. If you think about it, you can see that doubling the size of the list only increases the depth by 1

Blacksmithing is a Cheap wow gold buy wow power leveling aion wedding dresses  wow power leveling great profession, and for some classes it would be a very wise decision to make blacksmithing their profession. Mining should definitely be taken as your second profession if you wow gold decide to be a blacksmith because it will save you a lot of gold. Leveling blacksmithing is quite expensive even if you are a miner and doing it without it will costs you thousands of additional gold. wow power leveling Blacksmithing would be a perfect choice, especially for the plate users and melee DPS classes since most of the goodies that can be made only have a purpose for these classes.It must also be sad that the best craftable and usable items come in the end. Even though you might find some armors, items and weaponry that you are able to craft while you level worth equipping to boost your character a bit. wedding dresses Most of you probably know you need a Blacksmith Hammer to craft items and that most items can only be crafted at a forge. Forges can be found in all the major cities though, as well as in many smaller villages.We made this guide especially for the people that would like to minimize their costs and effort while leveling their blacksmithing aion power leveling profession.You will also notice that at one point you will be able cxyojhllkjhd to choose between becoming a weaponsmith, and then be able to choose from Axe, Mace and Sword smith, and an Armor smith. You will be able to redo your choice but this will be at a cost of 25G-100G, so choose wisely. cxy