Форум Flasher.ru - Задачка из серии "для экзаменаторов"

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - Задачка из серии "для экзаменаторов" (http://www.flasher.ru/forum/showthread.php?t=160508)

Задачка из серии "для экзаменаторов"

Вот пришел к нам работать новый человек и поделился задачкой (я запостю пару моих решений, но позже). Вопрос который ему задали на каком-то собеседовании (он вообще сам пишет на Яве, поэтому во Флеше может показаться немного надумано, но в общем вопрос, можно сказать, агностически-программистсткий).

Собственно задача: Нужно развернуть однонаправленный связанный список за O(n) время, естесственно минимальным n. Во Флеше это конечно немного усложняется тем, что нет канонической реализации связного списка, но для задачи, предположим, что он у вас есть :) Если хочется предложить свои варианты реализации - я бы смотрел в сторону HaXe, т.как там есть стандартный List, ну или вы можете воспользоваться FD + моим шаблоном (как-бы нет в нем ничего особенного, и сейчас я начинаю понимать, что можно было бы по-другому... и ах... но для этой задачи не принципиально http://code.google.com/p/e4xu/source...es/List.as.fdt ).

А в чем подвох?
Обычным for 0..n создаем список.

Код AS3:

var prev:Element;

for (var i:int = 0;  i< n; i++) 

{

        var element:Element = new Element();

        if(prev)

                element.prev = prev;

        prev = element;        

 

}

не? если нужен next сделаем список от n до 0

Нет, я видимо не правильно объяснил. Список уже есть, готовый, его нужно развернуть, т.е. чтобы последний элемент списка стал первым, предпоследний - вторым и т.д.

Котяра: а проверка зачем? :)

Array#reverse() ? :)

Сменить ссылку с последующего элемента на предыдущий и сделать последний элемент первым.

Цитата:

Сообщение от CrazyFlasher (Сообщение 1011463)

Array#reverse() ? :)

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

Код AS3:

var a:Array = [1,2,3,4,5];

 

for(var i:int = 0; i < a.length; i++){

        var f:int = a[i];

        var l:int = a[Math.abs(a.length - 1 - i)];

        a[i] = l;

        a[Math.abs(a.length-1 - i)] = f;

 

        var b:int = Math.round((a.length-1)/2);

        if(i+1 == b)break;

}

 

trace(a);

чото такое, что-ли

Код AS3:

function reverse(list:List):List {

        var l0:List = list;

        var l1:List = null;

        while(l0) {

                var tmpList:List= l1;

                l1 = l0;

                l0 = l0.next;

                l1.next = tmpList;

        }

        return l1;

}

извините, как переменные назвать - не придумал просто %)

Так-так-так, массивы тут не рассматриваются, и функцию нужно написать самому, а не взять готовую, в этом как бы и весь смысл (ну не знаю, представьте, что вы пишете на ассемблере, и готового ничего нет, даже libc).
Собственно, даже не обязательно написать на каком-то конкретном языке решение (можно просто на словах объяснить общий смысл), хотя, если оно внятно объясняет почему так, а не иначе, то, конечно, это тоже подходит.
Еще, для тех, кто не в курсе - вычислить длину связного списка - это уже O(n) операция, где n - длина списка. Так что решение, в котором нужно "сначала найти последний элемент, или длину" потенциально неудачные, т.как это значит, что список нужно перебрать как минимум 2 раза.

-De- - пока что ближе всех, но решение может быть меньшей алгоритмической сложности.

Да, я забыл сказать, если вдруг это будет принципиально для решения - циркулярные списки не рассматриваются, но это конечно замечательно, если решение будет работать и для них тоже :)

Мой, "пазорный" вариант)

Код AS3:

//создаём список

var a:Object = {i:0};

var first:Object = a;

for(var i:int = 1; i < 10; i++) {

        var next:Object = {i:i};

        a.link = next;

        a = next;

}

 

first = reverse(first);

//трейсим результат

while (first.link) {

        trace(first.i);

        first = first.link;        

}

trace(first.i);

 

 

function reverse(first:Object, next:Object = null) {

        if(next == null) {

                next = first.link;

                first.link = null;

        }

 

        var successor:Object = next.link;

        next.link = first;

 

        if(successor)

                return reverse(next, successor);

        else

                return next;

}