/**
 * 翻转链表非递归
 */
public ListNode q1(ListNode head){
      ListNode left =null;
      ListNode right =head;
      ListNode right2=head;

      while(right!=null){
          right2 = right.next;
          right.next = left;
          left = right;
          right = right2;

      }

      return left;

}


/**
 * 递归         先深入到底，再逆方向操作
 */

public ListNode q2(ListNode head){

    if(head==null || head.next==null){
      return head;
    }
    ListNode newHead = q2(head.next);
    head.next.next = head;
    head.next = null;

    return newHead;
}

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val,  ListNode next) { this.val = val; this.next = next; }
}