面试算法：单链表反转给定一个单链表，请将其反转并返回。示例：原链表：反向链表：定义的单链表节点类结构如下：/***单链表节点*/publicclassListNode{publicIntegervalue;接下来是公共ListNode；publicListNode(){}publicListNode(intvalue){this.value=value;}}先写两个方法，用来组装链表，并将链表打印到控制台，方便算法结果验证：/***组装成链表*/publicListNodeassemble(int[]items){if(items==null||items.length==0){返回null;}ListNodelist=newListNode(items[0]);ListNode节点=列表；对于(inti=1;i");}while(list!=null){System.out.print(list.value+"->");list=list.next;}System.out.println("null");}1.“栈”反转“栈”是一种先进后出（FILO）的数据结构，我们可以利用这个特性来实现反向链表。1）首先将链表节点按顺序入栈：2）然后开始将节点出栈，并将指针一个一个反转：为了最后返回反转后的链表，我们使用了一个topnodereference为栈顶节点指向它，通过top节点，可以在完成反向链表后按顺序访问完整反向链表的所有节点；另外，为了出栈时反转指针，再定义两个节点prev和rear，初始的prev和top指向同一个节点栈的栈顶节点，即反向链表的首节点.先弹出栈顶原链表的尾节点（反转链表首节点）5出栈：弹出节点4出栈（后节点），反转指向的指针4->5到5->4，这时节点4指向NULL，即不指向任何真实节点：prev节点向后移动一个节点位置，现在指向节点4，弹出节点3出栈（后节点），然后reverses将指针从3->4变为4->3：prev节点向后移动一个节点位置，现在指向节点3，将节点2出栈(rearnode)，然后将指针反转为2->3就是3->2：prev节点后退一个节点位置，现在指向节点2，将节点1出栈(rearnode)，thenreversedpointerto1->2is2->1:Done.3)代码实现：publicListNodereverseByStack(ListNodelist){//节点为空，或者只有一个节点，如果没有则不需要反转(list==null||list.next==null){返回列表；}//Deque双端队列可以实现“栈”数据结构函数Dequestack=newLinkedList<>();while(list!=null){//逐个推送：stack.addFirst(list);堆栈。推（列表）；list=list.next;}//弹出栈顶节点ListNodetop=stack.pop();ListNodeprev=top,rear;while(!stack.isEmpty()){//一个一个弹出栈：rear=stack.removeFirst();后部=stack.pop();//反向指针prev.next=rear;rear.next=null;//prev节点指针向后移动一个节点位置prev=rear;}返回ntop;}4）结果验证：int[]items=IntStream.generate(()->1+(int)(Math.random()*50)).limit(8).toArray();ListNodelist=assemble(items);System.out.print("原始单链表：");print(list);ListNoderlist=reverseByStack(list);System.out.print("反向单链表：");print(列表）；原始单链表：16->24->48->43->4->9->47->42->null反向单链表：42->47->9->4->43->48->24->16->null2。递归方法将原链表的节点依次递归到最后一层，即原链表的尾节点，并将尾节点的引用透明地传递回递归方法的第一层，在每一层中，将节点指针取反，然后方法返回注意：当链表长度过长时，该方法会抛出java.lang.StackOverflowError。1）将原链表的节点依次递归到最后一层，返回端节点5：2）透明返回端节点5，在每一层中，反转指向：端节点5的指针使用rlist引用指向它。注意，在反转指针的时候，不能使用rlist的引用来操作，因为在每一层递归中，都必须保证rlist向上是“透明”的，也就是说，它永远是5个节点。指向4->5的反向指针为5->4，此时节点4指向NULL，即不指向任何真实节点：指向3->4的反向指针变为4->3：反向指针指向2->3是3->2：反向指针指向1->2是2->1：完成。3）代码实现：publicListNodereverseRecursively(ListNodelist){//节点为空，或者只有一个节点，不需要反转//注意：递归函数的最后一级也会在这里返回：list。next==nullif(list==null||list.next==null){返回列表；}//递归函数透明的返回最后一个节点对上一层ListNode的引用rlist=reverseRecursively(list.next);//在递归函数的每一层，在将rlist引用透明传回上一层之前，递归地反转当前两个节点指向的指针，即反转原list->list.next为list.next->列表list.next.next=列表；list.next=null;returnrlist;}4)结果验证：int[]items=IntStream.generate(()->1+(int)(Math.random()*50)).limit(8).toArray();ListNodelist=assemble(items);System.out.print("原始单链表：");print(list);ListNoderlist=reverseRecursively(list);System.out.print("反向单链表：");print(rlist);原始单链表：44->28->3->11->49->3->20->13->null反向单链表：13->20->3->49->11->3->28->44->null3。In-placeinversion（单指针法）这种方法比较容易理解，就是依次迭代链表的所有节点，并且在每次迭代中，指针的调整需要增加两个指针引用到prev和rear，分别用于定位当前链表节点的上一个节点和下一个节点，方便指针调整操作。1）定义prev和rear节点引用，依次迭代链表节点：初始化prev为NULL，rear不指向任何节点：rear指向2个节点（当前节点列表的下一个节点），调整指针为1->2就是1->NULL，prev和list后移一个节点位置（此时prev指向1，list指向2）：rear指向节点3（当前节点的下一个节点）nodelist)，将指向2->3的指针调整为2->1，同时将prev和list向后移动一个节点位置（此时prev指向2，list指向3）：rear指向4个节点（当前节点列表下一个节点)，调整指向3->4的指针为3->2，并将prev和list向后移动一个节点位置（此时prev指向3，list指向4）：rear指向node5（当前节点列表的下一个节点），将指向4->5的指针调整为4->3，将prev和list向后移动一个节点位置（此时prev指向4和list指向5):rear指向NULL节点(当前节点链表的下一个节点)，将指针5->NULL调整为5->4，同时将prev和list向后移动一个节点位置(此时,prev指向5,list指向NULL):Done.2)代码实现:publicListNodereverseInSitu1(ListNodelist){//节点为空，或者只有一个节点，不需要反转if(list==空||list.next==null){返回列表；}//list为当前节点，prev为链表的上一个节点，rear为链表的下一个节点ListNodeprev=null,rear;while(list!=null){//1、暂存最后一步的rear节点引用，将list节点指针后移一个节点位置（最后一步会赋值：list=rear;）rear=list.下一个;//2.反转指针，即把原来的prev->list反转为list->prevlist.next=prev;//3.prev和list节点指针向后移动一个节点位置prev=list;列表=后方；}returnprev;}3)结果验证：int[]items=IntStream.generate(()->1+(int)(Math.random()*50)).limit(8).toArray();ListNodelist=assemble(items);System.out.print("原始单链表:");print(list);ListNoderlist=reverseInSitu1(list);System.out.print("反向单链表：");print(rlist);原始单链表：11->12->2->15->17->38->10->1->null反向单链表：1->10->38->17->15->2->12->11->null4。In-placeinversion(Doublepointermethod)这种方法和前面的方法类似，不同的是当前节点列表在每次迭代中并没有向后移动一个节点位置，而是指向后面的节点（当前节点的下一个节点）节点列表），该方法比“单指针法”少了一次迭代，需要增加两个指针指向prev和rear，用于定位当前链表节点的前一个节点（初等于当前节点）和后退节点，以方便指针调整操作。1）定义prev和rear节点引用，依次迭代链表节点：初始化prev指向1（和list指向同一个节点），rear不指向任何节点：rear指向3个节点（下currentnodelistNextnode)，将指向2->3的指针调整为2->1，将prev后移一个节点位置（此时prev指向2），然后将list指针设置为3（即1->2调整1->3，打破调整最后一个指针指向1->2->1形成的“环”：rear指向节点4（当前节点链表的下一个节点），而调整指针指向3->4就是3->2，将prev向后移动一个节点位置（此时prev指向3），再将链表指针指向4（即调整1->3为1->4，打破之前指向的指针调整1->3->2->1形成的“环”：rear指向节点5（当前节点链表的下一个节点），调整指针to4->5to4->3，将prev后移一个节点位置（此时prev指向4），然后将链表指针指向5（即调整1->4为1->5，breaking之前指向1->4调整形成的指针->3->2->1“环”）：rear指向NULL节点（当前节点链表中的下一个节点），调整指针为5->NULL到5->4，并向后移动prev移动一个节点位置（此时prev指向5），然后将链表指针指向NULL（即调整1->5为1->NULL，打破之前指向1->5->4->3调整形成的指针->2->1“环”）：完成。可以看出，“双指针法”的第一个指针是用来反转指针的，但是这样会形成一个“环”，而第二个指针是为了打破这个环，指向下一个的节点同时操作（后面的节点引用是为了保存它，以便list在每次迭代的最后一步找到并指向它）。2）代码实现：publicListNodereverseInSitu2(ListNodelist){//节点为空，或者只有单个节点，不需要反转if(list==null||list.next==null){returnlist;}//list为当前节点，prev为链表的前一个节点（初始等于当前节点），rear为链表的尾节点ListNodeprev=list,rear;while(list.next!=null){//1,暂存上一步要操作的rear节点的引用，从list切换到rear（最后一步会赋值：list.next=后方;)后方=list.next.next;//2.第一次调整指针(3个节点之间的第二个指针)，即调整原来的list.next->rear为list.next->prev，注意这一步会形成一个"响”list.next.next=prev;//3.prev节点指针向后移动一个节点位置，此时prev节点指针指向反向单链表的首节点prev=list.next;//4.第二次调整指针（3个节点之间的第一个指针），list节点指针指向rear节点，即list->rear，这一步用来打破“环”第二步形成的list.next=rear;}returnprev;}3)结果验证：int[]items=IntStream.generate(()->1+(int)(Math.random()*50)).limit(8).toArray();ListNodelist=assemble(items);System.out.print("原始单链表：");print(list);ListNoderlist=reverseInSitu2(list);System.out.print("反向单向链表：");打印（列表）；原始单链表：25->38->50->47->16->30->27->40->null反向单链表：40->27->30->16->47->50->38->25->null5。头部插值法头部插值法是在每次插入一个新元素时插入一个称为“头节点”的节点。“point”元素背后的方法在JDK7的java.util.HashMap类中也有应用1）定义一个临时的“头节点”tmpHead，rear节点引用，按顺序迭代链表节点，插入到tmpHead后面：初始化临时头节点tmpHead，rear节点引用不指向任何节点：rear指向节点2（当前节点列表的下一个节点），在tmpHead后面（节点NULL之前）插入节点1，将当前节点列表向后移动一个节点位置（此时list指向2）：rear指向节点3（当前节点列表的下一个节点），将节点2插入到tmpHead后面（节点1之前），将当前节点列表向后移动一个节点位置（thiswhenlist指向3）：rear指向4nodes（当前节点列表的下一个节点），在tmpHead后面（节点2的前面）插入节点3，将当前节点列表向后移动一个节点Position（此时list指向4）：rear指向节点5（当前节点列表的下一个节点），在tmpHead后面（节点3的前面）插入节点4，将当前节点列表向后移动一个节点位置（此时列表指向5）：rear指向NULL节点（当前节点列表的下一个节点），在tmpHead后面（节点4前面）插入节点5，将当前节点列表移动到然后向前移动一个节点位置（此时列表指向NULL）：Done.2)代码实现：publicListNodereverseByHeadInsertion(ListNodelist){//节点为空，或者只有一个节点，不需要反转if(list==null||list.next==null){返回列表；}//list为当前节点，tmpHead为临时头节点，rear为链表的下一个节点ListNodetmpHead=newListNode(),rear;while(list!=null){//1.暂存最后一步的rear节点引用将list节点的指针向后移动一个节点位置（最后一步会赋值：list=rear;）rear=列表.next;//2.在反向链表的头部后插入一个新节点（当前节点）tmpHeadlist.next=tmpHead.next;tmpHead.next=列表；//3.将当前节点的链表指针向后移动一个节点位置list=rear;}returntmpHead.next;}3)结果验证：int[]items=IntStream.generate(()->1+(int)(Math.random()*50)).limit(8).toArray();ListNodelist=assemble(items);System.out.print("原始单链表：");print(list);ListNoderlist=reverseByHeadInsertion(list);System.out.print("反向单链表：");打印（列表）；原始单链表：6->24->39->7->27->37->22->36->null反向单链表：36->22->37->27->7->39->24->6->空
