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

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

Ответ

Первая ссылка из гугла.
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; } }
Отсюда