本文共 2797 字，大约阅读时间需要 9 分钟。

大家好，我是烤鸭：

<<算法>> 第四版1.3.30

接受一条列表的首结点作为参数，（破坏性地）将列表反转并返回结果链表的首结点。

看了一下答案，说实话，看不太懂。

答案：

public Node
   
     reverse()  {      Node
    
      oldFirst = first;;      first = null;      while (oldFirst != null)      {          Node
     
       second = oldFirst.next;          oldFirst.next = first;          first = oldFirst;          oldFirst = second;      }      return first;  }
     
    
   

结合java中的Collections接口的reverse方法说一下 这是jdk1.8中的源码:

public static void reverse(List
    list) {    int size = list.size();    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {        for (int i=0, mid=size>>1, j=size-1; i
   
    >1; i
   

说一下 REVERSE_THRESHOLD = 18,RandomAccess是标记接口，表示集合类型。

简单的说,如果集合类是RandomAccess的实现，

则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历。

反过来，如果List是Sequence List，则最好用迭代器来进行迭代。

就是说集合长度小于18,并且是RandomAccess的类型，采用swap(list,i,j); 看一下swap()方法的源码:

public static void swap(List
    list, int i, int j) {    // instead of using a raw type here, it's possible to capture    // the wildcard but it will require a call to a supplementary    // private method    final List l = list;    l.set(i, l.set(j, l.get(i)));}

set方法:

E set(int index, E element);

get方法:

E get(int index);

看到这里，大概就明白了。

l.get(i)拿到i位置的值,

l.set(j, l.get(i)),把i位置的值放到j位置,并返回j位置的值。 l.set(i, l.set(j, l.get(i))),返回的j位置的值,放到i位置。

不得不佩服大神的逻辑。一行代码搞定。

再看一下数据量大,并且不属于RandomAccess接口的集合。

ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size);    for (int i=0, mid=list.size()>>1; i

创建两个ListIterator集合，说一下ListIterator和Iterator： Iterator迭代器包含的方法有： hasNext()：如果迭代器指向位置后面还有元素，则返回 true，否则返回false next()：返回集合中Iterator指向位置后面的元素 remove()：删除集合中Iterator指向位置后面的元素 ListIterator迭代器包含的方法有： add(E e): 将指定的元素插入列表，插入位置为迭代器当前位置之前 hasNext()：以正向遍历列表时，如果列表迭代器后面还有元素，则返回 true，否则返回false hasPrevious():如果以逆向遍历列表，列表迭代器前面还有元素，则返回 true，否则返回false next()：返回列表中ListIterator指向位置后面的元素 nextIndex():返回列表中ListIterator所需位置后面元素的索引 previous():返回列表中ListIterator指向位置前面的元素 previousIndex()：返回列表中ListIterator所需位置前面元素的索引 remove():从列表中删除next()或previous()返回的最后一个元素（有点拗口，意思就是对迭代器使用hasNext()方法时，删除ListIterator指向位置后面的元素；当对迭代器使用hasPrevious()方法时，删除ListIterator指向位置前面的元素） set(E e)：从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e 从api上看，ListIterator比Iterator强大很多。 但是： ListIterator只能用于List及其子类型，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。 所以针对list及其子类的话，ListIterator首选。 看一下list.listIterator()和list.listIterator(size); 这个size表示创建的listIterator，下标从第size个元素开始。 遍历集合，取出正向的listIterator，先保留下标元素。 正向的listIterator.set(反向的listIterator的对应位置的元素)。 举个例子： list = {1,2,3,4,5};

ListIterator fwd = list.listIterator(); // {1,2,3,4,5}下标在0

ListIterator rev = list.listIterator(5); // {1,2,3,4,5}下标在4 for (int i=0, mid = 2; i<mid; i++) {     Object tmp = fwd.next();     fwd.set(rev.previous());     rev.set(tmp); }    i=0的时候，list = {5,2,3,4,1} i=1的时候，list = {5,4,3,2,1}

转载地址：http://ibmlf.baihongyu.com/