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

[wvxvw]

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

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

[terbooter]

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

[Котяра]

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

[wvxvw]

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

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

[Котяра]

Сообщение от wvxvw

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

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

Ну вообще "развернуть" - это иногда подразумевает "создать".. типа развернуть сервер..
а проверка реально не нужно.. просто для первого элемента ещё prev нет.. ну и типа фиг с ним - и так и так null

[CrazyFlasher]

Array#reverse() ?

[Bgg]

Сообщение от CrazyFlasher

Array#reverse() ?

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

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

[iNils]

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

[-De-]

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

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

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

[wvxvw]

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

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

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