链表反序

链表反序是笔试面试中常考的一道题，其实现并不难，但是往往手写却并不容易写出来，这里记录一下链表反序的实现方法。

public class InverseList {
     private static class Node{
         public int data;
         public Node next;
         public Node(int data){
             this.data = data;
             this.next = null;
         }
     }
     
     private static class LinkList{
         private Node root;
         public LinkList(){
             this.root = null;
         }
         public void insert(int data){
             Node cur = root;
             if(root==null){
                 root = new Node(data);
                 return;
             }
             while(cur.next!=null){
                 cur = cur.next;
             }
             cur.next = new Node(data);
         }
         public Node inverseList(){
             Node cur = null;
             Node pre = null;
             Node next = null;
             if(root==null)
                 return root;
             cur = root;
             /*实现链表反序的核心代码*/
             while(cur!=null){
                 next = cur.next;
                 cur.next = pre;
                 pre = cur;
                 cur = next;
             }
          /*将root指向反序后的链表头*/
             root =pre;
             return root;
         }
         public void print(){
             Node cur = root;
             if(root==null)
                 return;
             while(cur!=null){
                 System.out.print(cur.data+" ");
                 cur=cur.next;
             }
         }
     }
     
     public static void main(String[] args){
         LinkList list = new LinkList();
         list.insert(4);
         list.insert(8);
         list.insert(9);
         list.insert(3);
         list.print();
         list.inverseList();
         System.out.println("\r\n"+"============");
         list.print();
         
     }
     
}

由以上代码可以发现，实现链表反序并不困难，主要在一个while循环中改变指针指向，然后将root节点指向反序后的链表头。