单链表插入排序

浏览数：36 / 时间：2015年06月08日

思想：把待排序的链表分为已经排序的链表，和剩余未排序的链表

例如：3->4->1->5->2->NULL

已经排序完毕的的链表：（从第一个数开始） 3->NULL

未排序完毕的链表：4->1->5->2 用p表示还未排序的剩余链表的首节点

例如：3->4->NULL ready

1->5->2->NULL

每次已经排序完毕的链表的尾节点的next指针都是NULL

ListNode* insertsort( ListNode*head){
     if(head==NULL||head->m_pNext==NULL) return head;
    
    
     ListNode* p=head->m_pNext;          //从第二个节点开始
     head->m_pNext=NULL;                 //首个元素next置为NULL
    while(p!=NULL){
         ListNode*temp=head;                    
        
         ListNode*prev=NULL;
         while(temp!=NULL&&temp->m_nValue<=p->m_nValue){
            prev=temp;
            temp=temp->m_pNext;
        }
        if(temp==NULL){
            prev->m_pNext=p;
             ListNode*last=p;
             p=p->m_pNext;
             last->m_pNext=NULL;
        }
        else if(temp->m_nValue>p->m_nValue){
             ListNode*first=p;
             p=p->m_pNext;
             first->m_pNext=head;
            head=first;
        }
        else {
            ListNode* mid=prev->m_pNext;
             ListNode*next=p;
             p=p->m_pNext;
             prev->m_pNext=next;
             next->m_pNext=mid;
        }
    }
    return head;
}