Вставка Сортировка для сортировки узлов в LinkedList

Question

Im пытается использовать метод сортировки вставки для сортировки узлов из LinkedList. Я скорректировал код столько раз, но я не могу, похоже, получить его, продолжать получать разные типы результатов, которые не сортируются.

Heres код:

Node* sort_list(Node* head) 
{ 
    Node* node_ptr = NULL; 
    for(Node* i = head->next; i->next != NULL; i = i->next){ 
      if (i->key < head->key) { 
       node_ptr = i; 
       head = head->next; 
    } 
    } 
    return node_ptr; 
} 

Answer 1

Это проблема домашних заданий, так вместо того, чтобы прямо писать код, я первым указать, где вы пошло не так.

В алгоритме сортировки, подобном вставке, очевидно, что требуется некоторая замена, которая должна выполняться между неуместными элементами (которые необходимо вставить). Поэтому начните с размышления о том, как вы можете поменять два элемента массива. Обратите особое внимание на случаи, когда один из них является голова или один хвост.

В вашем реализованном коде нет следов указателей, поэтому здесь вы ошибаетесь.

Далее вы должны подумать о случаях, когда нам нужно сортировать. В этом случае это довольно просто. Если текущий элемент и следующий находятся в отсортированном порядке (при условии возрастания, текущий < следующий). Тогда ничего не нужно делать, а просто сделать следующий поток.

Тогда вы, очевидно, можете заключить, что нарушение этого случая происходит, когда вам нужно поменять элементы. После обмена (с должным вниманием к тому, где указатели были и будут после сортировки), повторите процесс, пока не нажмете нулевую стену.

P.S: Это возможный дубликат другого вопроса.