剑指 Offer 24. 反转链表

解法一：迭代

使用三个变量，pre保存上一次遍历结束的节点，cur保存当前遍历到的节点，next保存下一个节点

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        ListNode pre=null,cur=head,next;
        while(cur!=null){
    
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}
//O(n)
//O(1)

解法二：递归

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if(head==null||head.next==null){
    //链表为空或者只有1个节点
            return head;
        }
        ListNode newHead=reverseList(head.next);//反转后面n-1个节点
        head.next.next=head;//原来的第2个节点指向旧的头节点
        head.next=null;//旧的头节点指向null
        return newHead;//返回新的头节点
    }
}
//O(n)
//O(n)