递归法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return NULL;
        if(!head->next) return head;
        ListNode* p = head->next;
        head->next = NULL;
        p = reverseList(p);
        ListNode* tail = p;
        while(tail->next) {
            tail = tail->next;
        }
        tail->next = head;
        return p;
    }
};

递推法(头插法)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return NULL;
        if(!head->next) return head;
        ListNode* preHead = new ListNode(0);
        ListNode* p = head;
        head = head->next;
        while(p) {
            p->next = preHead->next ;
            preHead->next = p;
            p = head;
            if(head) head = head->next;
        }
        return preHead->next; // 可以delete头节点
    }
};