3分钟学个算法链表反转

　　题目描述
　　输入一个链表，反转链表后，输出新链表的表头。
　　输入｛1，2，3，4，5｝
　　返回值｛5，4，3，2，1｝解题
　　初拿到这题，很容易联想到反转系列用java的api中提供了几个类似的api如Collections。reverse（）和StringBuilder。reverse（）。他们提供了直接对集合、字符串的反转api。需要的就是根据链表构建集合，再将集合反转，反转后再重新构建链表指向关系。代码如下：publicstaticListNodereverseByList（ListNodehead）｛方法先判断入参if（headnull）｛｝只有一个元素的直接返回if（head。nextnull）｛｝ListListNodelistnewArrayList（）；while（head！null）｛list。add（head）；headhead。｝直接使用Collections的reverse反转Collections。reverse（list）；反转后重建指向关系for（inti0；ilist。size（）1；i）｛list。get（i）。nextlist。get（i1）；｝链表最后一元素的next置为空list。get（list。size（）1）。returnlist。get（0）；｝
　　上面的方法确实能解决问题，但是一般出到这题，考的不会是你的api的熟练程度，面试官一般会要求你自己实现反转过程。对于集合的反转，自己实现的通用算法是index为i的和index为size1i的元素位置进行对调进行实现。集合原理图如下：
　　集合反转代码实现如下：publicstaticvoidreverseList（ListListNodelist）｛如果只有0或者1个元素，不需要做处理if（list。size（）1）｛｝intsizelist。size（）；inthalf（size1）1；从中号位遍历到0号位，将i位与size1i位进行互换实现集合的反转for（i0；i）｛ListNodetemplist。get（size1i）；list。set（size1i，list。get（i））；list。set（i，temp）；｝｝
　　对于链表反转，上面链表反转思路是转为集合，对集合进行互换位置反转，然后再重建指针指向。还有一种只针对链表反转更有效的方式，即直接改变指针指向即可。用一个pre保持指向之前的节点的指针，用一个current指针指向当前遍历节点。直接改变当前指针的指向，由指向下一个节点改造为指向前面的节点。原理图如下：
　　代码实现如下：publicstaticListNodereverseLinkNode（ListNodehead）｛方法先判断入参if（headnull）｛｝只有一个元素的直接返回if（head。nextnull）｛｝用于保持之前的指针，便于current指向ListNListNtemp用于保持当前节点的下一个节点的指针，使得遍历继续ListNwhile（current！null）｛tempcurrent。current。｝因为循环终止条件是到最后current为null了，链表的头节点应该是pre，即最后一个非空节点｝
　　还有没有其他思路？在集合反转的时候除了交换对称位置的元素，如果想到stack的FILO特性，也很方面的使用stack进行反转集合，但是要额外使用一个n大小的栈空间。时间复杂度都是O（n）。java中需要用栈可以用LinkedList实现。总结
　　对于链表反转主要两种思路：
　　一个是直接改变链表节点指针实现，即原先指向下一个节点的指针改为指向前一个节点，这种时间复杂度是O（n），空间复杂度是O（1），一次遍历完成，效率较高。
　　另一种即将链表转为集合，可以用Java的Collections。reverse（）直接反转或者用交换头尾元素的思路或者利用LinkedList的FILO特性用分别用addLast与pollLast方法进行添加和删除，反转集合后重建指针指向，这类思路，时间复杂度是O（n），空间复杂度是O（n）（因为创建新的列表需要空间，栈也同样需要），针对链表反转总体效率不如第一种。
　　END