insertion sort on a singly linked list

Am i right in thinking that it is not possible to perform insertion sort on a singly linked list?

My reasoning: assuming that insertion sort by definition means that, as we move to the righ开发者_如何学Ct in the outer loop, we move to the left in the inner loop and shift values up (to the right) as required and insert our current value when done with the inner loop. As a result an SLL cannot accomodate such an algorithm. Correct?

Well, I'd sound like the Captain Obvious, but the answer mostly depends on whether you're ok with keeping all iterations directed the same way as elements are linked and still implementing the proper sorting algorithm as per your definition. I don't really want to mess around your definition of insertion sorting, so I'm afraid you'd really have to think yourself. At least for a while. It's an homework anyway... ;)

Ok, here's what I got just before closing the page. You may iterate over an SLL in reversed direction, but this would take n*n/2 traversals to visit all the n elements. So you're theoretically okay with any traversal directions for your sorting loops. Guess it pretty much solves your question.

It is doable and is an interesting problem to explore.

The core of insertion sort algorithm is creating a sorted sequence with the first one element and extending it by adding new element and keeping the sequence is still sorted until it contains all the input data.

Singly linked list can not be traversed back, but you can always start from it's head to search the position for the new element.

The tricky part is when inserting node i before node j, you must handle their neighbor relationship well(I mean both node i and j's neighbor needs to be taken care of).

Here is my code. I hope it useful for you.

int insertSort(Node **pHead)
{
Node *current1 = (*pHead)->next;
Node *pre1 =*pHead;
Node *current2= *pHead;
Node *pre2=*pHead;
while(NULL!=current1)
    {
    pre2=*pHead;
    current2=*pHead;

    while((current2->data < current1->data))
    {
        pre2 = current2;
        current2 = current2->next;
    }
    if(current2 != current1)
    {
        pre1->next=current1->next;
        if(current2==*pHead)
        {
            current1->next=*pHead;
            *pHead = current1;
        }
        else
        {
            pre2->next = current1;
            current1->next = current2;
        }
        current1 = pre1->next;
    }
    else
    {
        pre1 = pre1->next;
        current1 = current1->next;
    }
}
return 0;

}