Реверсирование LinkedList в Java

Question

Я пытался использовать рекурсию, чтобы отменить LinkedList, но я получил странный результат, следующий мой код:

import java.util.LinkedList; 
import java.util.List; 

/** 
* Created by liqiushi on 2/6/14. 
*/ 
public class ReverseLinkedList { 
    public static void main(String[] args) { 
     List<Integer> list = new LinkedList<Integer>(); 
     list.add(1); 
     list.add(2); 
     list.add(3); 
     list.add(4); 
     list.add(5); 

     reverse(list, 0); 
     for (int i : list) { 
      System.out.println(i); 
     } 
    } 

    private static void reverse(List<Integer> list, int index) { 
     if (list == null) 
      return; 

     if (index == 5) { 
      return; 
     } 
     int currentVal = list.get(0); 
     list = list.subList(1, list.size()); 
     index += 1; 
     reverse(list, index); 

     list.add(currentVal); 
    } 
} 

результат для исполнения является: 1 2 3 4 5 5 4 3 2 1, где я ошибся?

P.S. Я попытался проанализировать временную сложность этого алгоритма, я думаю, что он должен быть O (n), поскольку он просто рекурсирует 4 раза, подобно дереву, в котором каждый узел имеет только один левый или правый дочерний элемент, исправьте меня, если я ошибаюсь.

Answer 1

В принципе, вы не должны использовать List#add, если вы хотите заменить элементы (а не добавить их).

Вы можете сделать следующее:

private static void reverse(final List<Integer> list, final int index) { 
    if (index >= list.size()) { 
     return; 
    } 

    final int currentVal = list.get(index); 
    reverse(list, index + 1); 
    list.set(list.size() - 1 - index, currentVal); 
} 

Хотя не является эффективным для LinkedList с, он будет работать. :)

---

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

private static List<Integer> reverse(final List<Integer> list, final int index) 

в принципе, в этом случае, вы бы:

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

Например:

private static List<Integer> reverse(final List<Integer> list, final int index) { 
    if (index >= list.size()) { 
     return new LinkedList<>(); 
    } 

    final List<Integer> res = reverse(list, index + 1); 
    res.add(list.get(index)); 
    return res; 
} 

(если вы сделаете это, не забудьте перебрать reverse(list, 0) и непосредственно не list в методе main)

---

Просто конечная точка , как отметил @Sundeep, в этом случае использование простого цикла было бы более эффективным - но мы считаем, что вы действительно хотите поиграть с рекурсией ... :)

Answer 2

Вы добавляете в список, который уже содержит 5 элементов. Если вам не нужны исходные элементы, вы должны добавить их в новый список.

Answer 3

Похоже, что есть непонимание базовых требований.

Рассмотрите это: вы хотите удалить все, кроме последнего элемента из списка.Мутирование списка (или подсписка) - плохая идея, так как то, что приводит к состоянию, не определяется естественной рекурсией.

Тем не менее, давайте отбросим несколько вещей:

• Лечить List передается как final - это сказать, что вы не можете передать ему или изменить его безопасно.

• Разрушить список, как вы рекурсивно. Каждый срез должен быть на один меньше, чем над ним. Верните a List, содержащий только этот фрагмент.

• Не волнует, насколько велик этот список. Рекурсия должна быть способна работать так глубоко, как позволит вам стек вызовов.

Это говорит ... подумайте:

private static <Type> List<Type> listToReverse(int index, final List<Type> list) { 
    final List<Type> reversedList = new ArrayList<>(); 
    if(index == list.size()) { 
     return reversedList; 
    } else { 
     reversedList.addAll(listToReverse(index++, list.subList(index, list.size()))); 
     reversedList.add(list.get(index - 1)); 
    } 
    return reversedList; 
} 

Я намеренно сделал это родовое и ушел из публичного вызова в качестве упражнения для читателя.

Помните, что базовый регистр - если текущее «индексное» местоположение, которое я читаю, эквивалентно размеру самого списка, мне нечего делать, поэтому я могу безопасно вернуть пустой список. Затем я постепенно начинаю добавлять элементы из индекса 0 в size - 1.

E.g. Если я сделаю этот рекурсивный вызов с начальной позицией индекса в 0, то к моменту, когда я ударил размер моего списка, я добавляю элемент в size - 1 в список.