Сторнирование списка через ListIterator

Question

Я получил задание, в котором я должен перевернуть список с одним или несколькими ListIterators. Мне не разрешено использовать метод collections.reverse() или другие подобные методы. Мне также не разрешено создавать новое поле. Я не могу просто использовать новый список. Вход должен быть изменен!

Это то, что я получил до сих пор. Но вход не изменился:

    public static <T> List<T> reverse(List <T> input) {
        ListIterator <T> listIterator2 = input.listIterator(input.size());
         ListIterator <T> listIterator =  input.listIterator(input.size());
         int u = input.size()-1;
         while(listIterator.hasNext()) {        
                 listIterator.next();
                while (listIterator2.hasPrevious()) {
                    listIterator.set(input.get(u));
                     listIterator2.previous(); 
                     u--;
                }
         }
         return input;
    }
   }

Answer 1

Вот способ рекурсивного решения проблемы:

static <T> void reverse(List<T> list) {
    reverse0(list.listIterator(), list.listIterator());
}

static <T> void reverse0(ListIterator<T> in, ListIterator<T> out) {
    if (in.hasNext()) {
        T t = in.next();
        reverse0(in, out);
        out.next();
        out.set(t);
    }
}

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

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

static <T> void reverse_nonrecur(List<T> list) {
    ListIterator<T> fwd = list.listIterator();
    ListIterator<T> rev = list.listIterator(list.size());
    while (rev.previousIndex() > fwd.nextIndex()) {
        T t = rev.previous();
        rev.set(fwd.next());
        fwd.set(t);
    }
}

Я избегал использования Collections.swap, так как это кажется ограничением проблемы (но вы не хотели бы использовать его для замены элементов, если список был LinkedList (но вы почти никогда не должны использовать LinkedList в любом случае)).

Answer 2

Использование ListIterator<T> для этой проблемы довольно странно, однако вот решение, которое повторяет список дважды. Здесь мы идем без использования Collections класса:

public static <T> List<T> reverse(List <T> input) {
    ListIterator<T> iterator = input.listIterator(input.size());
    List<T> reversedList = new ArrayList<>(input.size());
    while (iterator.hasPrevious()) {
        T temp = iterator.previous();
        reversedList.add(temp);
    }
    return reversedList;
}

Редактировать: я сделал ошибку. Метод ListIterator<E> listIterator(int index) предоставляет ListIterator, начиная с индекса. Поскольку вы начинаете с конца, вы можете выполнить итерацию один раз и добавить все элементы в новый список.

---

Edit2: не создавая новый список, я обнаружил, что вам нужно перебрать половину списка и получить элементы от конца / начала до середины и поменять их местами.

public static <T> List<T> reverse(List <T> input) {
    ListIterator<T> iterator = input.listIterator(input.size());
    ListIterator<T> reversedIterator = input.listIterator();
    for (int i=0; i<input.size()/2; i++) {
        T previous = iterator.previous();
        T next  = reversedIterator.next();
        iterator.set(next);
        reversedIterator.set(previous);
    }
    return input;
}

Answer 3

Как то так?

 private static <T> List<T> reverse(List<T> list) {
        ListIterator<T> fIterator = list.listIterator();
        ListIterator<T> bIterator = list.listIterator(list.size());
        for(int i = 0; i < list.size()/2; i++) {
            T backward = bIterator.previous();
            T forward = fIterator.next();
            bIterator.set(forward);
            fIterator.set(backward);
        }
        return list;
    }

Answer 4

Делать это с итераторами - странный способ, так как метод Collections.swap (который, вероятно, самый простой способ получить то, что вам нужно) специально запрашивает индексы. Так что, прежде всего, используйте их. Тем не менее, вы также можете сделать это с помощью итераторов. Это может выглядеть следующим образом:

public static <T> List<T> reverse(List<T> input)
{
    ListIterator<T> it = input.listIterator();
    ListIterator<T> itR = input.listIterator(input.size());

    while (it.nextIndex() - itR.previousIndex() < 0)
    {
        Collections.swap(input, it.nextIndex(), itR.previousIndex());
        it.next();
        itR.previous();
    }

    return input;
}

Вы начинаете с настройки итераторов. Один начинается в начале списка, другой в конце.

Тогда вы зацикливаетесь до тех пор, пока it.nextIndex() - itR.previousIndex() < 0. Это в основном перемещает оба итератора в центр списка без их пересечения, поэтому вы не можете поменять местами уже переставленные элементы.

Наконец, вы просто меняете элементы по соответствующим индексам и перемещаете итераторы.

Обновление

Поскольку вы указали, что вы не можете напрямую использовать Collections.swap (по любой причине), вы, очевидно, также можете заново изобрести колесо и просто переписать, что делает метод.

public static <T> List<T> reverse(List<T> input)
{
    ListIterator<T> it = input.listIterator();
    ListIterator<T> itR = input.listIterator(input.size());

    while (it.nextIndex() - itR.previousIndex() < 0)
    {
        T temp = input.get(it.nextIndex());
        input.set(it.nextIndex(), input.get(itR.previousIndex()));
        input.set(itR.previousIndex(), temp);

        it.next();
        itR.previous();
    }

    return input;
}

Точно так же, без использования (честно во всех случаях предпочтительного) метода Collections.swap.