讯享网

要求很简单，输入一个链表，反转链表后，输出新链表的表头。反转链表是有2种方法(递归法，遍历法)实现的，面试官最爱考察的算法无非是斐波那契数列和单链表反转，递归方法实现链表反转比较优雅，但是对于不了解递归的同学来说还是有理解难度的。

总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。递归法实现图

为了方便理解，我们以 1->2->3->4这个链表来做演示。输出的效果是4->3->2->1

首先定义Node：

 
 
   
 
 
  
    
  
package cn.liuhaihua;
 
  
    
  
public class Node<T> {
 
  
    
  
 Node next;
 
  
    
  
 T object;
 
  
    
  

 
  
    
  
 /
 
  
    
  
 * 构造函数
 
  
    
  
 * @param next
 
  
    
  
 * @param object
 
  
    
  
 */
 
  
    
  
 public Node(Node next,T object){
 
  
    
  
 this.next=next;
 
  
    
  
 this.object=object;
 
  
    
  
 }
 
  
    
  
}
 
 
   
 

反转方法如下：

讯享网 
 
   
 
 
  
    
  
 /
 
  
    
  
 * 递归反转
 
  
    
  
 * @param node
 
  
    
  
 * @return
 
  
    
  
 */
 
  
    
  
 public static Node reverse(Node node){
 
  
    
  
 Node newnode =null;
 
  
    
  
 if(null==node||null==node.next)
 
  
    
  
 {
 
  
    
  
 return node;
 
  
    
  
 }else{
 
  
    
  
 Node temp = node.next;
 
  
    
  
 newnode = reverse(node.next);
 
  
    
  
 temp.next = node;
 
  
    
  
 node.next=null;
 
  
    
  
 }
 
  
    
  
 print(newnode);
 
  
    
  
 return newnode;
 
  
    
  
 }
 
 
   
 

递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。

我们来看是怎样的一个递归过程：1->2->3->4

程序到达Node newnode = reverse(node.next);时进入递归 我们假设此时递归到了3结点，此时node=3结点，temp=3结点.next(实际上是4结点) 执行Node newnode = reverse(node.next);传入的node.next是4结点，返回的newnode是4结点。接下来就是弹栈过程了 程序继续执行 temp.next = node就相当于4->3 node.next = null 即把3结点指向4结点的指针断掉。返回新链表的头结点newnode

注意：当return后，系统会恢复2结点压栈时的现场，此时的node=2结点；temp=2结点.next(3结点)，再进行上述的操作。最后完成整个链表的翻转。

遍历法就是在链表遍历的过程中将指针顺序置换 

 
 
   
 
 
  
    
  
public static Node reverseList(Node node) {
 
  
    
  
 Node pre = null;
 
  
    
  
 Node next = null;
 
  
    
  
 while (node != null) {
 
  
    
  
 next = node.next;
 
  
    
  
 node.next = pre;
 
  
    
  
 pre = node;
 
  
    
  
 node = next;
 
  
    
  
 }
 
  
    
  
 return pre;
 
  
    
  
}
 
 
   
 

依旧是1->2->3->4 准备两个空结点 pre用来保存先前结点、next用来做临时变量 在头结点node遍历的时候此时为1结点 next = 1结点.next(2结点) 1结点.next=pre(null) pre = 1结点 node = 2结点 进行下一次循环node=2结点 next = 2结点.next(3结点) 2结点.next=pre(1结点)=>即完成2->1 pre = 2结点 node = 3结点 进行循环…

讯享网 
 
   
 
 
  
    
  
package cn.liuhaihua;
 
  
    
  

 
  
    
  
/
 
  
    
  
 *单链表反序
 
  
    
  
 */
 
  
    
  
public class NodeReverse {
 
  
    
  
 public static void main(String args[]){
 
  
    
  
 Node<String> node_d = new Node<String>(null,“D”);
 
  
    
  
 Node<String> node_c = new Node<String>(node_d,“C”);
 
  
    
  
 Node<String> node_b = new Node<String>(node_c,“B”);
 
  
    
  
 Node<String> node_a = new Node<String>(node_b,“A”);
 
  
    
  
 System.out.println(“反转前：”);
 
  
    
  
 print(node_a);
 
  
    
  
 System.out.println(“反转ing：”);
 
  
    
  
 //Node reversenode =reverse(node_a);
 
  
    
  
 Node reversenode = reverseList(node_a);
 
  
    
  
 System.out.println(“反转后：”);
 
  
    
  
 print(reversenode);
 
  
    
  

 
  
    
  

 
  
    
  

 
  
    
  
 }
 
  
    
  

 
  
    
  
 /
 
  
    
  
 * 递归反转
 
  
    
  
 * @param node
 
  
    
  
 * @return
 
  
    
  
 */
 
  
    
  
 public static Node reverse(Node node){
 
  
    
  
 Node newnode =null;
 
  
    
  
 if(null==node||null==node.next)
 
  
    
  
 {
 
  
    
  
 return node;
 
  
    
  
 }else{
 
  
    
  
 Node temp = node.next;
 
  
    
  
 newnode = reverse(node.next);
 
  
    
  
 temp.next = node;
 
  
    
  
 node.next=null;
 
  
    
  
 }
 
  
    
  
 print(newnode);
 
  
    
  
 return newnode;
 
  
    
  
 }
 
  
    
  

 
  
    
  
 /
 
  
    
  
 * 遍历反转
 
  
    
  
 * @param node
 
  
    
  
 * @return
 
  
    
  
 */
 
  
    
  
 public static Node reverseList(Node node) {
 
  
    
  
 Node pre = null;
 
  
    
  
 Node next = null;
 
  
    
  
 while (node != null) {
 
  
    
  
 next = node.next;
 
  
    
  
 node.next = pre;
 
  
    
  
 pre = node;
 
  
    
  
 node = next;
 
  
    
  
 print(pre);
 
  
    
  
 }
 
  
    
  
 return pre;
 
  
    
  
 }
 
  
    
  
 /
 
  
    
  
 * 遍历节点数据
 
  
    
  
 * @param node
 
  
    
  
 */
 
  
    
  
 public static void print(Node node){
 
  
    
  
 System.out.print(“node遍历：”+node.object.toString());
 
  
    
  
 while(node.next!=null){
 
  
    
  
 node = node.next;
 
  
    
  
 System.out.print(”–>“+node.object.toString());
 
  
    
  
 }
 
  
    
  
 System.out.println(”\n”);
 
  
    
  
 }
 
  
    
  
}