How do you sort a Linked List (singly connected) in O(n)?

This is not a place to post assignment. I am sick of people posting their assignment and hoping someone to answer it. No one's gonna solve your problem while you're in a job interview. Study hard keeping that in mind. This thing will only make you lazy and degrade your learning habbit. Try to learn from books and google it yourself. I'm sure there must be hundreds of solutions for this in google as this is a pretty popular problem.

FYI..this is not an assignment and I am not a college guy. I know how to sort in O(n^2) andO(nlogn), Just didn't know how to sort in O(n) and thought somebody could help me here in sajha..!!

I don't know the answer to your question. But the way this thread is headed, you might enjoy the following.
http://forums.sun.com/thread.jspa?threadID=565098&start=0

No, you can not sort in O(n) time. Sorting requires comparison and reinsertion of items, so it is almost impossible to do it in O(n) time unless you are starting off with empty or already sorted array.  

is O(n) worst case? if it is you might wanna try radix sort, counting sort or some other non-comparison based sorting technique.

i am confused  now.   O(n) is  just a reference to time??  or is it the number of objects required??

O(n) is the asymptotic upper bound of algorithm, the best case is known as big Sigma(n), and the average case is known as big Theta(n). O(n) is usually considered as it represents the worst case of an algorithm. There are notation such as small o(n) and small omega(n) which are upper and lower case but are not asymptotically bounded. 

I think here is a confusion
I was referring O(n) as Computational complexity.

O(n) is not the worst case running time.
The complexity order is { O(n^2), O(nlogn), O(n),  O(logn)}  worst case to best case respectively.

See the Order here

My answer for a simple explanation for big O notation was for 1987 AD. 

hmmm.. still confuses  me,  but  what worries me is that i am a cs major and i have never heard about these  logarithmic terms before.  i know i have to  take  some  more  classes related to  logarithms,  but just so that i get an idea,  at what level do we need to know all these?

i am technically 3rd year (recently transferred), but from looking at my required classes, it will still take  me about 3 more to graduate.(BSc in CS)

i do understand the assymptotic behaviour and all, but from the  maths classes i have taken, so i am guessing the term means the same.

http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/6_046J-2005-L02.pdf

, @ Gajedi: O(n) doesn't always mean worst-case its just the upper bound. Worst case means what is the maximum running time the sorting algorithm can take if the input is arranged in the worst order for that particular algorithm. For example, look at the table in http://en.wikipedia.org/wiki/Sorting_algorithm

@1987 AD: I studied this in my "Data Structures and Algorithms" class. It was a 300-level course @ my univ where courses are upto 400-level max in undergrad. It is very important for programming and other applications. The saying goes like, " You can either program for 10 years and be a good programmer, or your can take an alogrithms class and be one in 3 :)"

Sarkar123,

@Gajedi: Notations (sigma, O, theta)  and cases (worst, average, best) are different things.

http://lcm.csa.iisc.ernet.in/dsa/node9.html

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

@wai wai: I think the sorting you wanna do is Bucket sort. Though I am not very familiar with that one!

Sarkar, Are you sure they are different than the notations? Please read the whole thing in the link you have provided and not just one page talking about big O. 

@Wai_Wai
What type of value does the List contains. If it's an integer then what will be the range??
As someone previously suggested, the sorting algorithm will depend on the type of value in the List.

There are couple of options:
1. Use a Heap (min heap). First insert all, then remove one by one. -- o(nlogn)
2. Use a lookup array. i.e. something like bucket sort. O(n + m) where n is the size of the list and m is the size of the lookup array
3. Insert all and remove all from a BST. -- O(nlogn)

For the requirement of O(n) I would rather go for bucket sort like algorithm:
First determine the range of values in the list.
And sort it based on the value or alternatively create a new List with those values.

@ Gajedi: They might look alike but they are different. Big-O doesn't HAVE to be a worst case. How would you then explain the best case running time of an insertion sort to be O(n), average case to be O(n²) and worst case be O(n²)? A worst case running time could have a Theta(n) or a Omega(n) notation (sorry in the previous thread I wrote sigma for omega). It all depends. Normally for sorting we use big-O in ALL cases (be it worst, average or best). But for other things, for eg. the worst case running time of inserting or finding a key in a hash table is always Theta(n).

I have the following lecture from UCBerkeley that might make it clear for you. The link to this lecture is http://www.eecs.berkeley.edu/~jrs/61b/lec/21 . Scroll down the paragraph before the title "ALGORITHMIC ANALYSIS"

"Remember that the choice of O, Omega, or Theta is _independent_ of whether
we're talking about worst-case running time, best-case running time,
average-case running time, memory use, annual beer consumption as a function of
population, or some other function. The function has to be specified.
"Big-Oh" is NOT a synonym for "worst-case running time," and Omega is not a
synonym for "best-case running time."