Sword finger offer 24. reverse the linked list

Solution 1 ： iteration

Use three variables ,pre Save the node at the end of the last traversal ,cur Save the currently traversed node ,next Save the next node

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)

Solution 2 ： recursive

class Solution {
    
    public ListNode reverseList(ListNode head) {
    
        if(head==null||head.next==null){
    // The linked list is empty or only 1 Nodes 
            return head;
        }
        ListNode newHead=reverseList(head.next);// Reverse behind n-1 Nodes 
        head.next.next=head;// The original second 2 Nodes point to the old head node 
        head.next=null;// The old head node points to null
        return newHead;// Return to the new header node 
    }
}
//O(n)
//O(n)