ALLInterview.com :: Home Page KalAajKal.com
 Advertise your Business Here     
Browse  |   Placement Papers  |   Company  |   Code Snippets  |   Certifications  |   Visa Questions
Post Question  |   Post Answer  |   My Panel  |   Search  |   Articles  |   Topics  |   ERRORS new
   Refer this Site  Refer This Site to Your Friends  Site Map  Bookmark this Site  Set it as your HomePage  Contact Us     Login  |  Sign Up                      
info       Did you received any Funny E-Mails from your Friends and like to share with rest of our friends? Yeah!! you can post that stuff   HERE
Google
 
Categories >> Code-Snippets >> Programming-Code >> C-Code
 
 
 
Question
How do you sort a Linked List (singly connected) in O(n)
please mail to pawan.10k@gmail.com if u can find an
anser...i m desperate to knw...
 Question Submitted By :: Pawan
I also faced this Question!!     Rank Answer Posted By  
 
Answer
struct NODE
{
int nodevalue;
struct NODE *next;
}
struct NODE *uslist, *slist;
struct NODE *cur_us, *cur_s; /*pointers to surf the lists*/
main()
{
..
/*uslist and slist have been initialised here*/
/*uslist holds the list to be sorted*/
/*slist is initially empty as nothing is sorted*/
..
..
LLsort();
}

LLsort ( )
{
int delval; 
struct NODE *temp;

slist->nodevalue = 0; /*sorted list will have 0 as its first
element initially*/
slist->next = NULL;
cur_us = uslist;

while( cur_us != NULL)
{
  cur_s = slist;  
 while(cur_s != NULL)
  {
   if(cur_us->nodevalue < cur_s->nodevalue)    /*step-1 of
the algo.*/
   {
    target = cur_s;    /*step-2: make cur_s as your TARGET*/
    delval = delnode(cur_us); /*deletion has to be done to
the UNSORTED list*/
    addnode(delval, target);  /*remember addition has to be
done to the SORTED list*/
   }
   else
     if(cur_s->next == NULL)   /*step-3:if cur_s is the last
element in the sorted list*/
       {
        delval = delnode(cur_us);
        temp_us = (struct NODE *)malloc(sizeof(NODE));   
        temp_us ->nodevalue = delval;
        cur_s->next = temp_us;   /*step-3:append the
unsorted element to the sorted list*/
        temp_us->next = NULL;
       }
   cur_s = cur_s->next;  
  }
cur_us = cur_us->next;
}
}
 
0
Ajaay
 
View All Answers
 
 
 
 
 
   
Copyright Policy  |  Terms of Service  |  Help  |  Site Map 1  |  Articles  |  Site Map  |   Site Map  |  Contact Us interview questions urls   External Links 
   
Copyright © 2007  ALLInterview.com.  All Rights Reserved.

ALLInterview.com   ::  Forum9.com   ::  KalAajKal.com