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

[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]

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

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

[CrazyFlasher]

Array#reverse() ?

[iNils]

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

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

[-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- - пока что ближе всех, но решение может быть меньшей алгоритмической сложности.

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

[nuToH]

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

//создаём список
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;
}