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; 
}