Реверсирование элементов списка с помощью рекурсии

Question

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

public static List<Integer> reverse(List<Integer> input) {
    if (input.isEmpty()) {
        return new LinkedList<Integer>();
    } else {
        List<Integer> output = new LinkedList<Integer>();
        output.add(((LinkedList<Integer>) input).removeLast());
        reverse(input);
        return output;
    }
}

К сожалению, я получаю только первый элемент правильно, остальная часть списка просто не отображаетсявверх.Чего мне не хватает?

Answer 1

// This will work for you

    public static void main(String[] args) {
            List<Integer> input = new LinkedList<Integer>();
            List<Integer> output = new LinkedList<Integer>();
            input.add(5);
            input.add(1);
            input.add(3);
            int size = input.size();
            System.out.println(reverse(input, size, output));

        }

        public static List<Integer> reverse(List<Integer> input, int sizeOfInput, List<Integer> output) {

            if (sizeOfInput > 0) {
                output.add(((LinkedList<Integer>) input).removeLast());
                sizeOfInput--;
                reverse(input, sizeOfInput, output);
            }
            return output;
        }

Answer 2

Как упоминалось в комментариях, вам нужен второй параметр и, вероятно, не нужно возвращаемое значение:

public static void reverse(List<Integer> input, List<Integer> output) {
    if (input.isEmpty()) {
        return;
    }
    output.add(((LinkedList<Integer>) input).removeLast());
    reverse(input, output);
}

Использование:

List<Integer> input = new LinkedList<>();
// fill it with values
List<Integer> output = new LinkedList<>();

reverse(input, output);
System.out.println(output);

Answer 3

Вы можете сделать это, как показано ниже.Обратите внимание, что я использую метод removeFirst().

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

public class Reverse {

  public static List<Integer> reverse(List<Integer> input) {
    if (input.isEmpty()) {
      return new LinkedList<Integer>();
    } else {
      Integer first = ((LinkedList<Integer>) input).removeFirst();
      List<Integer> output = reverse(input);
      output.add(first);
      return output;
    }
  }

  public static void main(String[] args) {

    List<Integer> input = new LinkedList<>();
    input.add(15);
    input.add(37);
    input.add(26);
    input.add(18);
    input.add(31);

    System.out.println("Input  : " + input);
    System.out.println("Output : " + reverse(input));
  }
}

Answer 4

Я использую для удобства Stack для его метода pop.

public static List<Integer> reverse(List<Integer> input) {
    Stack<Integer> stack = new Stack();
    stack.addAll(input);
    return reverse(stack,new LinkedList<>());
  }

  public static List<Integer> reverse(Stack<Integer> input,LinkedList<Integer> output) {
     if (input.isEmpty()) {
       return output;
     }
     output.addFirst(input.pop());
     reverse(input, output);
    return output;
  }

Если вы хотите пропустить повторное добавление элементов, вам необходимо поддерживать индекс или использовать LinkedList, который знаетиз первого и последнего элемента.Вот с сохранением индекса и чистого API списка:

public static List<Integer> reverse(List<Integer> input) {


     return reverse(input,new LinkedList<>(),0);
  }

  public static List<Integer> reverse(List<Integer> input,LinkedList<Integer> output,int index) {
     if (index == input.size()) {
       return output;
     }
     output.addFirst(input.get(index));
     reverse(input, output,++index);
    return output;
  }