Bubble сортировать связанный список

Question

У меня есть эти два структур, которые строят в связный список:

struct Element { 
    int value; 
    struct Element *next; 
}; 

struct List { 
    struct Element *first; 
}; 

Теперь я хочу, чтобы отсортировать список, связанный с пузырьковой сортировки. Я реализовал метод sortList, который сравнивает значение текущего элемента со значением следующего элемента. Если значение следующего элемента больше текущего, оно должно быть заменено. Но в данный момент это работает неправильно.

void sortList(List *list) { 
    Element *current = malloc(sizeof(Element)); 
    current = list->first; 
    Element *nextElement = malloc(sizeof(Element)); 
    nextElement = current->next; 
    Element *tmp = malloc(sizeof(Element)); 
    tmp = NULL; 

    int changed = 1; 
    while (changed) { 
     changed = 0; 
     for (current; (current != NULL) && (nextElement != NULL);) { 
      if (current->value > nextElement->value) { 
       tmp = current->next; 
       current->next = nextElement->next; 
       nextElement->next = tmp; 
       changed = 1; 
      } 
      current = current->next; 
      nextElement = nextElement->next; 
     } 
    } 
} 

Answer 1

После перезагрузки, перед повторным запуском, вы должны установить текущий и следующий элемент, указывающий начало списка! Или они не меняются, и тестовое условие для сбоя происходит немедленно. Кроме того, в чем смысл маллоков? вы используете current, next и temp только как указатель на узел, а не как настоящий узел, я думаю, что вы можете удалить все из них. И вы можете переписать это как-то с условием только, это более читаемо. Извините за мой английский.

EDIT: как написано под вопросом, вам нужно изменить указатель внутри списка. Я думаю, что самым простым способом является немедленное перемещение нижнего элемента в начале списка и изменение главы списка, чтобы указать этот элемент. После этого сортировки остальная часть списка.

Answer 2

Предполагая, что программа сортирует существующий список, нет причин выделять узлы в sortList, это должно просто манипулировать указателями на существующие узлы.

При замене узлов необходимо обновить указатель, указывающий на текущий узел, который может быть list.first или Element.next. Использование указателя на указатель делает это немного проще.

struct Element **ppcur; /* pointer to list->first or element->next */ 
/* ... */ 
    if(list == NULL || list->first == NULL) 
     return NULL; 
    for(ppcur = &(list->first); pnxt = (pcur = *ppcur)->next; 
     ppcur = &((*ppcur)->next)){ 
    /* ... */