▼

14 нояб. 2012 г.

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

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

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

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

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

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

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

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

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

  1. Unknown14 ноября, 2012 11:24

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

    ОтветитьУдалить
  2. Unknown14 ноября, 2012 12:40

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

    }

    ОтветитьУдалить
  3. Анонимный14 ноября, 2012 20:41

    /**
    * @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;
    }

    ОтветитьУдалить
  4. Konstantin Andreev14 ноября, 2012 23:51

    http://pastebin.com/trce0hmt

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

    ОтветитьУдалить
  5. Unknown22 ноября, 2012 09:22

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

    ОтветитьУдалить