Задан односвязанный список, например:
A -> B -> C -> ... -> X -> Y -> Z
Необходимо развернуть список, т.е, чтобы его крайний элемент стал первым, предпоследний вторым, и т.д, и в конце концов, первый элемент стал бы крайним элементом.
Z -> Y -> X -> ... -> C -> B -> A
Сложность: O(N), доступная память: O(1).
замечание: можно модифицировать исходный список.
A -> B -> C -> ... -> X -> Y -> Z
Необходимо развернуть список, т.е, чтобы его крайний элемент стал первым, предпоследний вторым, и т.д, и в конце концов, первый элемент стал бы крайним элементом.
Z -> Y -> X -> ... -> C -> B -> A
Сложность: O(N), доступная память: O(1).
замечание: можно модифицировать исходный список.
внимание! комментарии содержат ответ.
5 комментариев:
Надо просто развернуть ссылки в узлах списки то есть '->' поменять на '<-'
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;
}
http://pastebin.com/trce0hmt
Ну в принципе тоже что и у предыдущего комментатора
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 + '}';
}
}
Отправить комментарий