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