剑指24.反转链表

迭代：
空间复杂度：O(1);

class Solution {
    public ListNode reverseList(ListNode head) {
                if(head==null){
                    return null;
                 }
                ListNode cur=head; //定义当前节点
                ListNode pre=null; 
                while(cur!=null){
                     ListNode ncur=cur.next;
                     cur.next=pre;
                     pre=cur;
                     cur=ncur;
                }
                return pre;
            }
        }

递归
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
               if(head==null||head.next){
                     return head;
                }
             ListNode newHead=reverseList(head.next);
             head.next.next=head;
             head.next=null;
             return newHead;
            }
        }