在面试，笔试的过程中经常会遇到面试官问这种问题，实现单链表的倒置方法。现在对单链表的倒置犯法做个记录，方便自己以后查看。
单链表的定义：
1 public class Node { 2 3 int v; 4 Node next; 5 public Node(){ 6 } 7 public Node(int v){ 8 this.v = v; 9 } 10 11 public int getV() { 12 return v; 13 } 14 public void setV(int v) { 15 this.v = v; 16 } 17 public Node getNext() { 18 return next; 19 } 20 public void setNext(Node next) { 21 this.next = next; 22 } 23 }
单链表的倒置方法有两种：递归的和非递归的。下边分别介绍：
递归：
1 public static Node reverse(Node head){ 2 if(head == null || head.next==null){ 3 return head; 4 } 5 Node reverseHead = reverse1(head.next); 6 head.getNext().setNext(head); 7 head.setNext(null); 8 return reverseHead; 9 }
非递归：
1 /** 2 * 非递归实现 3 * @param head 4 * @return 5 */ 6 public static Node reverse(Node head){ 7 if (head == null) return head; 8 Node pNode=head; 9 Node cur = head.next; 10 Node nNode=null; 11 while(cur!=null){ 12 nNode = cur.next; 13 cur.setNext(pNode); 14 pNode = cur; 15 cur = nNode; 16 } 17 head.setNext(null); 18 return pNode; 19 }
递归与非递归的实现和斐波那契函数的非递归实现很像。