Rorschach - 1 year ago 64
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;

{
//insert at top
Node* to_insert = (Node*)malloc(sizeof(Node));
to_insert->data = val;
}

{
//base case, iterated trough entire list
return NULL;

int max = 0;
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
}

//find node with max value
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

}

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

fix like this

``````Node *sort_ll(Node* head){
return head;//There is no need for processing

Node *to_move = NULL;

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