通过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

在这个问题上使用ListIterator是相当奇怪的，但是下面是迭代列表两次的解决方案。这里我们不需要使用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 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 2

这里有一种递归解决问题的方法：

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 3

使用迭代器这样做是一种奇怪的方法，因为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方法的情况下进行完全相同的操作。