复杂度O（n）倒转链表

 1 public class ListNode {
 2      int val;
 3      ListNode next;
 4      ListNode(int x) { val = x; }
 5      ListNode(){}
 6 
 7       public static ListNode revese(ListNode input)
 8     {
 9         ListNode head = new ListNode();//头插法的头
10         ListNode cur = input;                 //指向当前位置
11         ListNode headnext , next;          //两个龙套用于记下next 
12         while (cur != null)
13         {
14             headnext = head.next;   //龙套1登场
15                 next = cur.next;             //龙套2登场
16             head.next = cur;            //cur插到头后边
17             cur.next = headnext;      //连接龙套1
18             cur = next;                    //龙套2变成当前位置
19         }
20         return head.next;                  
21     }
22 }