209. insertion sort of linked list
Microsoft Interview Questions and Answers
(Continued from previous question...)
209. insertion sort of linked list
Question:
insertion sort of linked list
maybe an answer:
insertion sort in the singly list list always takes the O(n2) time in best case also
and worst case also the time complexity would be the same
code for it
void InsertionSort(struct node *L)
{
struct node *temp1,*temp2;
int tempval;
if(!L||!(L->next))
return ;
temp1=L->next;
while(temp1)
{
for(temp2=L;temp2->data<temp1->data && temp2!temp1;temp2=temp2->next);
if(temp2!=temp1)
{
key=temp2->data;
temp2->data=temp1->data;
temp2=temp2->next;
while(temp2!=temp1)
{
tempval=temp2->data;
temp2->data=key;
key=tempval;
temp2=temp2->next;}
tempval=temp2->data;
temp2->data=key;
key=tempval;
temp2=temp2->next;}
}
}
}
(Continued on next question...)
Other Interview Questions
|