Сортировка отдельно Связанный список

Question

void NodeList::sortNodeAscending() 
{ 
Node* swap = NULL; 
Node* saveLink = NULL; 


for(Node* firstPointer = head; firstPointer;firstPointer = firstPointer->next) 
    for(Node* secondPointer = firstPointer->next; secondPointer;secondPointer = secondPointer->next) 
    { 
     if((secondPointer->studentId)<(firstPointer->studentId)) 
     { 
      swap =firstPointer; 
      saveLink = secondPointer->next; 
      firstPointer = secondPointer; 
      secondPointer = swap; 

      firstPointer->next = secondPointer; 

      secondPointer->next = saveLink; 


     } 
    } 
} 

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

Выход:
{ 5, 0, 1, 2, 3, 4, 12, 15}

Все элементы сортируются кроме первого узла.

Примечание: Я уже проверял вопрос по ссылке ниже и отличается от моего вопроса. Sorting a Singly Linked List With Pointers

Answer 1

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

Answer 2

Сортировка список не так просто, как кажется в вашем коде:

[prev1] [first] [next1] ... [prev2] [second] [next2] 

должен выглядеть следующим образом на обмен первого со вторым:

[prev1] [second] [next1] ... [prev2] [first] [next2] 

Как сделать:

1. Магазин next1 или next2 и хранить трек prev1 и prev2 все время, как вы не можете оглянуться назад в одиночном списке.
2. first->next = next2 и second->next = next1
3. prev1->next = second и prev2->next = first

Во время всего этого, вам нужно обратить особое внимание на Лист head.

Answer 3

Как указал Кенни Остром, даже если проблемы с головой исправлены, если начальная последовательность идентификаторов студента равна 5,3,1,4,2, то сортировка заканчивается 5,1,3, а не сортировка и потеря двух значений.

Код заменяет firstPointer и secondPointer, которые используются в качестве внутренних и внешних переменных цикла. Это создает проблему.

При замене узлов в связанном списке узлы могут быть смежными (три следующих указателя повернуты), или они могут быть несмежными (две пары следующих указателей меняются местами). Чтобы обрабатывать оба случая с одним и тем же кодом, сначала замените все точки на два узла, которые должны быть сначала обменены (например, swap prev1-> next with prev2-> next), затем замените следующие указатели двух узлов (например, swap curr1-> next with curr2-> следующая).

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

Было бы проще начать с пустого «отсортированного» списка, затем удалить один узел за раз из исходного списка и вставить узел в нужное место в «отсортированный» список. Для этого метода начинайте с Node * sorted = NULL; Как только все узлы были удалены из исходного списка и вставлены в порядке сортировки, установите head = sorted, чтобы головка указывала на отсортированный список.

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