14 нояб. 2012 г.

Задачка: развернуть односвязанный список

Задан односвязанный список, например:

A -> B -> C -> ... -> X -> Y -> Z

Необходимо развернуть список, т.е, чтобы его крайний элемент стал первым, предпоследний вторым, и т.д, и в конце концов, первый элемент стал бы крайним элементом.

Z -> Y -> X -> ... -> C -> B -> A

Сложность: O(N), доступная память: O(1).

замечание: можно модифицировать исходный список.

внимание! комментарии содержат ответ.

5 комментариев:

slonnik3 комментирует...

Надо просто развернуть ссылки в узлах списки то есть '->' поменять на '<-'

slonnik3 комментирует...

class OneWayList {
// list head
Node head;
/** node class*/
class Node{
//next node
Node next;
//node value
T value;
}
// constructor
public OneWayList(T... values){
Node previous = null; //previous node
for(T value : values){
Node node = new Node();
node.value = value;
if(previous != null){
previous.next = node;
}
else{
head = node;
}
previous = node;
}
}
@Override
public String toString(){
StringBuilder builder = new StringBuilder("[");
Node node = head;
while(node != null){
String value = (node.value != null) ? node.value.toString() : "null";
builder.append(value + " ");
node = node.next;
}
builder.append("]");
return builder.toString();
}

}

public class ReverseList {

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

}
}

public static void main(String[] args){
OneWayList list = new OneWayList(new Integer[]{1,2,3,4,5});
System.out.println(list);
reverse(list);
System.out.println(list);
}

}

Анонимный комментирует...

/**
* @param head - голова списка [a_1, ..., a_n]
* @return голова списка [a_n, ..., a_1]
*/
public static Element reverse(Element head){
Element reversed = null;
// инвариант цикла:
// reversed - перевёрнутый список - [a_(k-1), ..., a_1]
// head - ещё нет - [a_k, ..., a_n]
while(head != null){
// отцепляем элемент от головы
Element standalone = head;
head = head.next;
// и прицепляем в голову перевёрнутого списка
standalone.next = reversed;
reversed = standalone;
}
return reversed;
}

Konstantin Andreev комментирует...

http://pastebin.com/trce0hmt

Ну в принципе тоже что и у предыдущего комментатора

Eugene Kravchenko комментирует...

class Node {
V value;
Node next;

static Node reverse(Node before, Node current) {
if (current == null)
return before;

Node b = current;
Node c = current.next;
current.next = before;

return reverse(b, c);
}

public static Node reverse(Node head) {
Node tail = reverse(head, head.next);
head.next = null;
return tail;
}

@Override
public String toString() {
return "Node{value=" + value + '}';
}
}