Insertion Sort List

Sort a linked list using insertion sort.

#include<stdio.h>
#include<stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
 }ListNode;

ListNode *insertionSortList(ListNode *head) {
    ListNode *p1,*p2,*p3,*p4,*p5;
    if(head==NULL || head->next==NULL) return head;
    for(p2=head,p1=head->next;p1!=NULL;){
        for(p4=p3=head;p3!=p1;p3=p3->next){
            if(p3->val>p1->val) break;
            p4=p3;
        }
        //printf("p3 %d,p1 %d\n",p3->val,p1->val);
        if(p3!=p1){
            p5=p1->next;
            p1->next=p3;
            if(p3==head){
                head=p1;
            }
            else{
                p4->next=p1;
            }
            p2->next=p5;
            p1=p5;
        }
        else{
            p2=p1;
            p1=p1->next;
        }
    }
    return head;
}

void main(){
    ListNode *head,*p1,*p2;
    int n=0;
    head=NULL;
    p1=p2=(ListNode *)malloc(sizeof(ListNode));
    scanf("%d",&p1->val);
    while(p1->val!=0){
        n++;
        if(n==1) head=p1;
        else p2->next=p1;
        p2=p1;
        p1=(ListNode *)malloc(sizeof(ListNode));
        scanf("%d",&p1->val);
    }
    p2->next=NULL;
    for(p1=head;p1!=NULL;p1=p1->next) printf("%d ",p1->val);
    printf("\n");
    p1=insertionSortList(head);
    while(p1!=NULL){
        printf("%d ",p1->val);
        p1=p1->next;
    }
    printf("\n");
}

Insertion Sort List

原文：http://blog.csdn.net/uj_mosquito/article/details/41744893