C：リンクリストの再帰的ソート

Question

リンクリスト構造の再帰ソートアルゴリズムを実装しようとしています。 C言語。 1））リスト 2で最大値を見つけ、リストから削除し、次のノード 4から再びヘッドノード 3）アルゴリズムを開始する時にそれを挿入）を使用すると、リストの最後に到達するまで実行します。

私のアルゴリズムはこれです

私は何かを持っていますが、私のリストを覚えていません。私はどこかでミスを犯していることを知っています（おそらく再帰呼び出し）が、それを修正する方法を理解することはできません。

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