4

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

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

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

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

3

2 ответа 2

5

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

3

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

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;
    }
}

Отсюда

1
  • И, да, @Schepalin, учитесь гуглить
    – The_Netos
    3 апр 2016 в 18:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.