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...

Answers were Sorted based on User's Feedback



How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / rashid akhtar

We cant sort a singly list list in O(n) that is sure.
We can sort an array in O(k+n) if k is order of n,otherwise
counting sort is also not of O(n).
So moral of story,nobody can sort a singly list in O(n)...

Is This Answer Correct ?    4 Yes 3 No

How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / alexht

Counting sort is a solution. Kormen 's book will help you.

Is This Answer Correct ?    2 Yes 4 No

How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / sunil gupta

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct node
{
int info;
struct node *next;
}node;
node *temp,*ptr,*t=NULL,*end=NULL;
node *start=NULL;

void main()
{
int n,i,item;
clrscr();
i=0;
printf("enter num of node");
scanf("%d",&n);
while(n>0)
{
temp=(node*)malloc(sizeof(node));
temp->next=NULL;

printf("enter info");
scanf("%d",&item);
temp->info=item;
if(start==NULL)
{
start=temp;
}
else
{
ptr=start;
while(ptr->next!=NULL)
{

ptr=ptr->next;
}
ptr->next=temp;

} //else
n--;
}

ptr=start;
while(ptr!=NULL)
{
printf("%d",ptr->info);
ptr=ptr->next;
}
t=start;
while(t!=NULL)
{
ptr=t->next;
while(ptr!=NULL)
{
if(t->info>ptr->info)
{
temp->info=t->info;
t->info=ptr->info;
ptr->info=temp->info;
}
ptr=ptr->next;
}
t=t->next;
}

ptr=start;
while(ptr!=NULL)
{
printf("\n%d",ptr->info);
ptr=ptr->next;
}
getch();
}

Is This Answer Correct ?    1 Yes 3 No

How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / hakr

Using Radix sort its the best solution it takes O(n).

typedef struct node *ptr;
struct node{
int element;
ptr next;
};
typedef ptr LIST;
typedef ptr POSITION;
int main()
{
.
.
.
.

for(i=0;i<10;i++)
{
p=A[i]->next;
while(A[i]->next!=NULL)
{
A[i]->next=p->next;
p->next=NULL;
digit=(p->element/pow(10,j))%10;
InsertLast(B[digit],p);//InsertLast is a function that
takes an int and position and then does as the name tells//
p=A[i]->next;
}
.
.
.
.
}

Is This Answer Correct ?    0 Yes 3 No

How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / abc

singly linked lists can be sorted in minimum of O(n2) [n
square] time.

Is This Answer Correct ?    2 Yes 10 No

How do you sort a Linked List (singly connected) in O(n) please mail to pawan.10k@gmail.com if u ca..

Answer / ajaay

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;
}
}

Is This Answer Correct ?    3 Yes 11 No

Post New Answer

More C Code Interview Questions

write a program in c language to get the value of arroy keys pressed and display the message which arrow key is pressed?

1 Answers  


why nlogn is the lower limit of any sort algorithm?

0 Answers  


main() { int i=10,j=20; j = i, j?(i,j)?i:j:j; printf("%d %d",i,j); }

2 Answers   Adobe, CSC,


How we print the table of 3 using for loop in c programing?

7 Answers  


#include <stdio.h> int main(void) { int a=4, b=2; a=b<<a+b>>2 ; printf("%d",a); return 0; }

0 Answers   Student,






how to return a multiple value from a function?

5 Answers   Wipro,


void main() { while(1){ if(printf("%d",printf("%d"))) break; else continue; } }

1 Answers  


why do you use macros? Explain a situation where you had to incorporate macros in your proc report? use a simple instream data example with code ?

0 Answers  


String copy logic in one line.

11 Answers   Microsoft, NetApp,


print a semicolon using Cprogram without using a semicolon any where in the C code in ur program!!

35 Answers   Tata Elxsi, TCS, VI eTrans,


What is "far" and "near" pointers in "c"...?

3 Answers  


main(){ char a[100]; a[0]='a';a[1]]='b';a[2]='c';a[4]='d'; abc(a); } abc(char a[]){ a++; printf("%c",*a); a++; printf("%c",*a); }

2 Answers  


Categories