双链表-双链表的排序（非节点值排序，而是节点排序）-蒲公英云

双链表-双链表的排序（非节点值排序，而是节点排序）

双链表的排序
#include <stdio.h>
#include <stdlib.h>
// 双链表
typedef struct node_t{ 
    int val;
    int idx;
    struct node_t *next, *prev;
}in, *in_p;
void  showList( struct node_t *h )
{ 
    printf("++++++++++++showList+++++++++++++\n");
    while( h ){ 
        printf("h->idx = %d , h->val = %d\n", h->idx, h->val );
        h = h->next;
    }
}
void  showRList( struct node_t *h )
{ 
    printf("+++++++++++showReverse++++++++++++++\n");
    while( h->next ){ 
        h = h->next;
    }
    while( h ){ 
        printf("h->idx = %d , h->val = %d\n", h->idx, h->val );
        h = h->prev;
    }
}
void insertHead( struct node_t **h, struct node_t *n )
{ 
    n->next = *h;
    if( *h != NULL ){ 
        (*h)->prev = n;
    }
    *h = n;
}
void insertTail( struct node_t **h, struct node_t *n )
{ 
    if( *h == NULL ){ 
        *h = n;
        return;
    }
    struct node_t *p = *h;
    while( p->next ){ 
        p = p->next;
    }
    p->next = n;
    n->prev = p;
}
in_p sort_list(in_p h){ 
    in_p newhead = NULL, min = NULL, head = NULL;
    while(h){ 
        min = h;
        head = h;
        while(head->next){ 
            if(min->val > head->next->val){ 
                min = head->next;
            }
        head = head->next;
        }
        if(min == h){ 
            h = h->next;
        }
        else{ 
            min->prev->next = min->next;
            if(min->next){                                         //以防最后一个节点是最小值，如果没有这判断，可能段错误
                min->next->prev = min->prev;
            }
        }
        min->next = NULL;                                        //
        min->prev = NULL;                                        //让min指向的这个节点完全脱开链表
        min->next = newhead;
        if(newhead != NULL){ 
            newhead->prev = min;
        }
        newhead =  min;
    }
    return newhead;
}
int main()
{ 
    int arr[] = { 10,10,9,8,5,20,10,10,30,20,10,10};
    struct node_t *head = NULL;
    int i = 0;
    struct node_t *newnode = NULL;
    while( i < sizeof(arr)/sizeof(int) ){     
        newnode = malloc( sizeof(struct node_t) );    
        newnode->val = arr[i];
        newnode->idx = i;
        newnode->next = NULL;
        newnode->prev = NULL;
        insertTail( &head , newnode );    
    // head = insertTail( head, newnode );
    // insertTail1( &head, newnode );
        i++;
    }
    showList( head );    
    head = sort_list(head);
    showList( head );    
    return 0;
}