要求很简单，输入一个链表，反转链表后，输出新链表的表头。反转链表是有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;
