输入
{1,2,3,4,5}
返回值
{5,4,3,2,1}解题
初拿到这题，很随意马虎遐想到反转系列用java的api中供应了几个类似的api如Collections.reverse()和StringBuilder.reverse()。他们供应了直接对凑集、字符串的反转api。须要的便是根据链表构建凑集，再将凑集反转，反转后再重新构建链表指向关系。代码如下：
publicstaticListNodereverseByList(ListNodehead){//方法先判断入参if(head==null){returnnull;}//只有一个元素的直接返回if(head.next==null){returnhead;}List<ListNode>list=newArrayList<>();while(head!=null){list.add(head);head=head.next;}//直策应用Collections的reverse反转Collections.reverse(list);//反转后重修指向关系for(inti=0;i<list.size()-1;i++){list.get(i).next=list.get(i+1);}//链表末了一元素的next置为空list.get(list.size()-1).next=null;returnlist.get(0);}
上面的方法确实能办理问题，但是一样平常出到这题，考的不会是你的api的闇练程度，口试官一样平常会哀求你自己实现反转过程。对付凑集的反转，自己实现的通用算法是index为i的和index为size-1-i的元素位置进行对调进行实现。凑集事理图如下：
凑集反转代码实现如下：
publicstaticvoidreverseList(List<ListNode>list){//如果只有0或者1个元素，不须要做处理if(list.size()<=1){return;}intsize=list.size();inthalf=(size-1)>>1;//从中号位遍历到0号位，将i位与size-1-i位进行互换实现凑集的反转for(inti=half;i>=0;i--){ListNodetemp=list.get(size-1-i);list.set(size-1-i,list.get(i));list.set(i,temp);}}
对付链表反转，上面链表反转思路是转为凑集，对凑集进行互换位置反转，然后再重修指针指向。还有一种只针对链表反转更有效的办法，即直接改变指针指向即可。用一个pre保持指向之前的节点的指针，用一个current指针指向当前遍历节点。直接改变当前指针的指向，由指向下一个节点改造为指向前面的节点。事理图如下：
代码实现如下：
publicstaticListNodereverseLinkNode(ListNodehead){//方法先判断入参if(head==null){returnnull;}//只有一个元素的直接返回if(head.next==null){returnhead;}//用于保持之前的指针，便于current指向ListNodepre=null;ListNodecurrent=head;//temp用于保持当前节点的下一个节点的指针，使得遍历连续ListNodetemp;while(current!=null){temp=current.next;current.next=pre;pre=current;current=temp;}//由于循环终止条件是到末了current为null了，链表的头节点该当是pre，即末了一个非空节点returnpre;}
还有没有其他思路？在凑集反转的时候除了交流对称位置的元素，如果想到 stack 的 FILO 特性，也很方面的利用 stack 进行反转凑集，但是要额外利用一个n大小的栈空间。韶光繁芜度都是O(n)。java中须要用栈可以用LinkedList实现。
总结对付链表反转紧张两种思路：
一个是直接改变链表节点指针实现，即原来指向下一个节点的指针改为指向前一个节点，这种韶光繁芜度是O(n)，空间繁芜度是O(1)，一次遍历完成，效率较高。
另一种即将链表转为凑集，可以用Java的Collections.reverse()直接反转或者用交流头尾元素的思路或者利用LinkedList的 FILO特性用分别用addLast与pollLast方法进行添加和删除，反转凑集后重修指针指向，这类思路，韶光繁芜度是O(n)，空间繁芜度是O(n)（由于创建新的列表须要空间，栈也同样须要），针对链表反转总体效率不如第一种。
- END -
