Сортировка структура, которая содержит указатель на следующий

Question

поэтому у меня есть что-то вроде:

struct Something 
{ 
    int number; 
    Something* next; 
}; 

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

Как бы я это сделал?

Я знаю, что конец и начало «список» (FIFO порядка)

Answer 1

Сортировать -> для каждого элемента отсортированного обновления массива следующего указателя

Answer 2

Существует различные алгоритмы сортировки (http://www.sorting-algorithms.com/), и, безусловно, я бы использовал случайный выбор для этого примера. Это будет выглядеть примерно так:

void Something::SortAscending() { 
    Something* current = next; 
    Something* smallest = next; 
    while(current) { 
     if(current->number < smallest->number) { 
     smallest = current; 
     } 
     current = current->next; 
    } 
    if(smallest != next) 
     smallest->next = next; 
    next = smallest; 
    next->SortAscending(); 
} 

Заметим, однако, что если вы дали голову списка, вы не можете изменить его с типом функции I, представленной выше.

Answer 3

Использовать MergeSort для связанных списков: сначала пересечь список двумя указателями пробега, один из которых продвигается в два раза медленнее. Когда вы достигаете конца списка, медленный указатель указывает на середину. Разделите список и отсортируйте половинки рекурсивно, затем Merge.