Сортировка узлов (Linked-list) C++

Question

Я пытаюсь сортировать связанный список. У меня есть узел, называемый head, и он указывает на следующий узел и т. Д.

Но когда я пытаюсь сортировать узлы по значению, которое они несут, я получаю сортировку, потому что вижу, что она распечатывает материал в if -statement, но я не вернусь к связанному списку. Где я неправ?

Node* head; 
void sortlist(){ 

Node * runner = head; 
Node * runner2; 

for(runner = head; runner->next != NULL; runner = runner->next){ 
    for(runner2 = runner->next; runner2->next != NULL; runner2 = runner2->next){ 
     if(runner->freq < runner2->freq){ 
      cout<< runner->freq<< " is LT "<<runner2->freq<< endl; 
      Node * temp = runner; 
      runner = runner2; 
      runner2 = temp; 
     } 
    } 
} 

head = runner; 
} 

Я только возвращаю первый узел.

Answer 1

Для того, чтобы обменять два элемента в связанном списке, считают, что вам нужно изменить. Например, чтобы получить от

Head -> First -> Second -> (NULL) 

в

Head -> Second -> First -> (NULL) 

вам нужно обновить: Head.next, First.nextиSecond.next. Вы не меняете любых тех вещей, которые пытаются обменять узлы, чтобы они не могли делать то, что вы ожидаете.

---

Просто поменять местами значения (т.е. swap(runner->freq, runner2->freq)) было бы намного проще.

Answer 2

вы остановитесь, когда runner->next == NULL;, который должен быть последним элементом. А затем вы установите head = runner;, что означает, что голова всегда будет последним элементом после этой процедуры. Более того, я не верю в эту замену.

Кажется, вы смутно хотите сделать insertion sort. Если вы хотите сделать простую сортировку по связанным спискам, я предлагаю вам использовать selection sort: вы создаете еще один пустой список l2 и каждый раз, когда вы удаляете минимальный элемент из своего первого списка и добавляете его в качестве главы l2. Код для второго списка прост:

void prepend(Node* node, Node** list){ 
    //null checks if you want 
    node->next = *list; 
    *list=node->next; 
}