关于单链表的反转，阿芬之前写过一篇文章，是通过迭代实现的。另一种方法是使用递归来实现。阿芬一直不敢写，怕自己说不清楚。但是又不能因为怕说不清楚就停止写，对吧？所以本文使用递归来实现，尽量把细节一一切掉，废话不多说。首先我们要先了解什么是递归。递归就是调用自己，对吧？比如：有一个函数f(n)=f(n-1)*n，（注意我这里是举个例子，这个函数没有给出递归结束条件）给n赋值5，那么:-->f(5)-->5*f(4)-->5*(4*f(3))-->5*(4*(3*f(2)))-->5*(4*(3*(2*f(1))))-->5*(4*(3*(2*1)))-->5*(4*(3*2))-->5*(4*6)-->5*24-->120看完例子，直接上代码，不BB了：/***单链表反转---递归实现*/publicclassReverseSingleList{publicstaticclassNode{privateintdata;privateNodeext;publicNode(intdata,Nodeext){this.data=data;this.next=next;}publicintgetData(){returndata;}}publicstaticvoidmain(String[]args){//初始化单链listNodenode5=newNode(5,null);Nodenode4=newNode(4,node5);Nodenode3=newNode(3,node4);Nodenode2=newNode(2,node3);Nodenode1=newNode(1,node2);//调用reversemethodnoderecursiveList=recursiveList(node1);System.out.println(recursiveList);}/***单链表反转的递归实现*@paramlist是incoming单链表*/publicstaticNoderecursiveList(Nodelist){//如果链表为空或者链表中只有一个节点，直接返回//也是递归结束的条件if(list==null||list.next==null)returnlist;Noderecursive=recursiveList(list.next);//指向list.next.next指针指向当前链表listlist.next.next=list;//指向list.next指针tonulllist.next=null;//返回反向链表recursivereturnrecursive;}}经过上面的代码，你应该能看到核心代码就是递归实现单链表反向部分的5行代码。别小看这5行代码，真的很难看懂把这5行代码贴在这里，我们逐行分析，看完这篇博文尝试理解~（去掉注释，重点关注这几行核心代码）if(list==null||list.next==null)returnlist;Noderecursive=recursiveList(list.next);list.next.next=list;list.next=null;returnrecursive;第一行是判断，条件不满足，然后往下走，第二行是调用自己，程序返回到第一行。如果不满足条件，则程序向下执行，自调用自身循环，直到条件满足。那么什么时候满足条件呢？即list==null或list.next==null时，看自己定义的链表是1->2->3->4->5->null，所以当条件满足时，此时链表为5->null。条件满足后，程序继续向下执行。执行代码行后Noderecursive=recursiveList(list.next);看看此时程序执行的结果：上面是我画的（粉丝画的不错，不用管它的美丑~）接下来，程序应该执行list.next.next=list执行结束后，链表是这样的：就是这张图，下面是程序断点调试程序的结果，发现和上图一样是一样的：程序继续执行往下走list.next=null，也就是把list的next指针指向null：从图中可以看出，list是4->null，递归是5->4->null，让我们看一下程序的结果，是不是和图片一致：是不是一模一样？好的，还记得我们刚刚开始的递归函数示例吗？现在执行完毕，我们开始下一次执行。我们继续看此时的链表看起来是这样的：程序接下来执行的代码是四行：Noderecursive=recursiveList(list.next);list.next.next=list;list.next=null;返回递归；继续执行程序，看看结果，运行完list.next.next=list，此时链表为：从图中可以看出，链表list为3在->4->3->4循环中，递归为5->4->3->4->3循环，我们看看程序是否一样（这里我切了两个循环作为例子）：Next，程序执行list.next=null。执行完成后，将list的next指针指向null：从图中可以看出，list是3->null，递归是5->4->3->null。看上图，看看实际结果和分析是否一致：什么意思？！说明我们上面的分析是正确的。读者可以在接下来的程序分析中自行研究。相信接下来的分析对于我们聪明的读者来说不会有难度。啦~把单链表的前N个节点倒过来就OK了。趁热打铁吧。刚才通过递归把整个单链表倒过来了。如果我只想反转前N个节点怎么办？比如单链表是1->2->3->4->5->null，现在我只想把前三个节点倒过来，变成3->2->1->4->5->null有什么想法吗？我们把整个单链表倒过来的时候，可以理解为传入一个参数n，这个n就是单链表的长度，然后递归程序不断的调用自己，然后就是整个单链表被逆转。那么，如果我要反转前N个节点，是不是要传一个参数n来解决呢？直接上代码：/***反转单链表的前n个节点*@paramlist是单链表传入的??，n是要反转的前n个节点*/publicstaticNodeext;publicstaticNodereverseListN(Nodelist,intn){if(n==1){//反转链表时，先将list后面的节点数据保存到nextnext=list.next;returnlist;}Nodereverse=reverseListN(list.next,n-1);list.next.next=list;//将list.next的指针指向链表list不反向。next=next;returnreverse;}单链表的一部分反转现在已经实现了整个单链表的反转，前N个节点已经反转了，如果需要反转一部分怎么办的数据？大概是这样的，结果链表是1->2->3->4->5->null，并且其中的一部分是反向的，这样反向链表就是1->4->3->2->5->null借用了倒序前N个节点的思路，我是不是应该传入两个参数，一个是开始倒序的节点，一个是倒序结束的节点，然后递归操作就是足够的？看看代码是怎么写的：/***单链表的逆向部分*@paramlist是传入的单链表，m是开始逆向的节点，n是结束逆向的节点*/publicstaticNodereverseBetween(Nodelist,intm,intn){if(m==1){returnreverseListN(list,n);}list.next=reverseBetween(list.next,m-1,n-1);returnlist;}最后，我已经弄清楚了最后两个例子。读者可自行研读。这里因为篇幅问题就不分析了。如果第一个例子能分析清楚，后面两个问题不大~实现的思路是借鉴网上的，真是高明，分享给大家。最后，为了看到阿粉在调试程序和画图帮助大家理解，大家要不要点个赞啊？
