在链表中交换两个元素

Question

有没有一种方法可以在不删除和重新插入的情况下交换链表中的两个元素？我目前使用的代码是：

void exchange(int i, int j) {
    int[] temp = matrix.get(i);
    matrix.remove(i);
    matrix.add(i, matrix.get(j - 1));
    matrix.remove(j);
    matrix.add(j, temp);
}

其中matrix是我的链表。

- Jon

---

如果你想通过索引访问元素，在Java中，LinkedList是一个不好的选择。考虑使用ArrayList或Vector。 - DwB

Answer 1

使用Collections对象中的swap方法：http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#swap%28java.util.List,%20int,%20int%29。该方法可以用于对List中指定索引位置的元素进行交换。

- jzd

---

我该如何开始实现它？ - Jon

Collections.swap(matrix, i, j) 交换集合中索引为i和j的元素。 - jzd

不幸的是，Collections#swap() 对于链表而言是2倍的 *O(n)*。请参见 LinkedList#entry(int)，它被 LinkedList#set(int, T) 使用。这很遗憾。 - seh

Answer 2

如果你必须自己实现它，这样做可以起作用：

void exchange(int i, int j) {
    ListIterator<int[]> it1 = matrix.listIterator(i),
                        it2 = matrix.listIterator(j);
    int[] temp = it1.next();
    it1.set(it2.next());
    it2.set(temp);
}

作为这样的技术，这将是：

void exchange(int i, int j) {
    matrix.set(i, matrix.set(j, matrix.get(i)));
}

第二种方法类似于如何实现Collections.swap。第一种方法对于长链表略微更有效率。

- finnw

Answer 3

matrix.set(i, matrix.set(j, matrix.get(i)));

- ring bearer