Java 单链表的倒置

在面试，笔试的过程中经常会遇到面试官问这种问题，实现单链表的倒置方法。现在对单链表的倒置犯法做个记录，方便自己以后查看。

单链表的定义：

 public class Node {

     int v;

     Node next;

     public Node(){

     }

     public Node(int v){

         this.v = v;

     }

     public int getV() {

         return v;

     }

     public void setV(int v) {

         this.v = v;

     }

     public Node getNext() {

         return next;

     }

     public void setNext(Node next) {

         this.next = next;

     }

 }

单链表的倒置方法有两种：递归的和非递归的。下边分别介绍：

递归：

 public static Node reverse(Node head){

         if(head == null || head.next==null){

             return head;

         }

         Node reverseHead = reverse1(head.next);

         head.getNext().setNext(head);

         head.setNext(null);

         return reverseHead;

     }

非递归：

 /**

      * 非递归实现

      * @param head

      * @return

      */

     public static Node reverse(Node head){

         if (head == null) return head;

         Node pNode=head;

         Node cur = head.next;

         Node nNode=null;

         while(cur!=null){

             nNode = cur.next;

             cur.setNext(pNode);

             pNode = cur;

             cur = nNode;

         }

         head.setNext(null);

         return pNode;

     }

递归与非递归的实现和斐波那契函数的非递归实现很像。