Теория по односвязному списку

#алгоритм #структуры_данных

Здравствуйте. 

Довольно часто на собеседованиях или же в тестовых заданиях (для прохождения на стажировку,
например) задается вопрос об односвязных списках.

Например, дают задачу, в которой необходимо развернуть односвязный список за О(n)
времени. Так вот, как это сделать? Можно ли просто переопределить ссылки? Т.е. сделать
за 1 итерацию так, чтобы не A->B, а A<-B ? 

Можете, пожалуйста, привести пример? 
Заранее благодарю
    

Ответы

Ответ 1

Первая ссылка из гугла.

void reverse(OneWayList list){
    OneWayList.Node node = list.head;
    OneWayList.Node previous = null;
    while(node != null){
         //next item
         OneWayList.Node tmp = node.next;
        //swap items
        node.next = previous;
        previous = node;
        list.head = node;
        //next item
        node = tmp;
    }
}


Отсюда


Ответ 2

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