Rorschach Rorschach - 15 days ago 6
C Question

C: Recursive sorting of linked list

I'm trying to implement a recursive sorting algorithm for linked list structure. C language.

My algorithm is this:
1) find max value in list
2) remove it from the list and insert it at Head node
3) start algorithm again from next node
4) run until you reach end of list

I have something, but it doesn't 'remember' my list. I realize I'm making a mistake somewhere (probably recursive calls), but I can't understand how to fix it.

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

fix like this

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