Если бы можно было создавать узлы, то согласно правилу стека (FILO), узлы нового списка после поузельного копирования были бы упорядочены как надо.
Долго ломал голову и пришел к следующему алгоритму.
Вид узла списка:
struct Node
{
int value;
Node *link;
};
typedef Node* NodePtr;
Список:
NodePtr head;
...
Необходимы следующие указатели на список:
- start = head; - первый элемент списка
- before_end = head; - предпоследний элемент списка
- end = NULL; - конец списка
- iter - для прохождения через список циклом for
Переменная для пузырьковой сортировки:
int temp;
Код: Выделить всё
for(iter = head; iter != end; iter = iter->link) //проходим по всему списку
{
before_end = before_end->link;
}
//По окончанию прохождения по списку, before_end, теоретически, должен указывать на предпоследний элемент
//но почему-то он проскакивает дальше
//Меняем значения первого и последнего элементов списка местами
temp = start->value;
start->value = iter->value;
iter->value = temp;
start = start->link; //следующий не упорядоченный элемент
end = before_end; //предыдущий неупорядоченный элемент
before_end = start; //поиск предпоследнего элемента
Условия окончания упорядочивания приблизительно представляю:
- прогонять цикл, пока после последних 3 строк before_end == end.
Но проверка алгоритма срывается после первого цикла for. Если список представляет из себя: 1 3 2 5 4, то во время цикла before_end указывает на 3 2 5 4 и выскакивает за пределы списка, завершая программу ошибкой.
Что не так работает? Корректен ли алгоритм или есть проще варианты?
