C：鏈表的遞歸排序

Question

我想實現鏈表結構的遞歸排序算法。 C語言。

我的算法是這樣的： 1）找到列表 2最大值）從列表中刪除，並在頭節點 3）啓動算法再次從下一個節點 4插入）運行，直到到達列表的末尾

我有一些東西，但它不記得我的清單。我意識到我在某處犯了一個錯誤（可能是遞歸調用），但我無法理解如何解決它。

typedef struct Node{ 
int data; 
struct Node* next; 
} Node; 

void insert(Node** head, int val) 
{ 
     //insert at top 
     Node* to_insert = (Node*)malloc(sizeof(Node)); 
     to_insert->data = val; 
     to_insert->next = (*head); 
     (*head) = to_insert; 
} 

Node* sort_ll(Node* head) 
{ 
    //base case, iterated trough entire list 
    if(head == NULL) 
     return NULL; 

    int max = 0; 
    Node* tmp = head; 
    Node* to_move = tmp; 

    //find maximum value 
    while(tmp != NULL) { 
     if(tmp->data > max) { 
      max = tmp->data; 
      to_move = tmp; 
     } 
     tmp = tmp->next; 
    } 

    //if its currently top, leave it there 
    if(to_move == head) { 
     return sort_ll(head->next); 
    } 

    //find node with max value 
    tmp = head; 
    while(tmp->next != to_move) { 
     tmp = tmp->next; 
    } 

    //cut it out from the list 
    tmp->next = tmp->next->next; 
    free(to_move); 

    //insert value at the head of the list 
    insert(&head, max); 

    return sort_ll(head->next); 
} 

int main() 
{ 
    Node* list = NULL; 

    insert(&list, 3); 
    insert(&list, 6); 
    insert(&list, 7); 
    insert(&list, 2); 
    insert(&list, 1); 
    insert(&list, 5); 
    insert(&list, 4); 

    list = sort_ll(list); 

    Node* tmp = list; 

    while(tmp != NULL) { 
     printf("%d\n", tmp->data); 
     tmp = tmp->next; 
    } 


    return 0; 
} 

Answer 1

修復此類

Node *sort_ll(Node* head){ 
    if(head == NULL || head->next == NULL) 
     return head;//There is no need for processing 

    int max = head->data; 
    Node *prev = head; 
    Node *to_move = NULL; 
    Node *tmp = head->next; 

    //find maximum value in rest(head->next) 
    while(tmp != NULL) { 
     if(tmp->data > max) { 
      max = tmp->data; 
      to_move = prev;//save previous node for remove link 
     } 
     prev = tmp; 
     tmp = tmp->next; 
    } 

    if(to_move == NULL) {//not find in rest 
     head->next = sort_ll(head->next); 
     return head; 
    } 

    prev = to_move; 
    to_move = prev->next;//max node 
    prev->next = prev->next->next;//max node remove from link 
    to_move->next = sort_ll(head); 
    return to_move; 
}