反转链表的三种方法–面试必考（图例超详细解析，小白一看就会！！！）-CSDN博客

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

方法1：就地逆置，三指针迭代
分不太清头插法和就地逆置的区别，感觉没啥区别。
三个指针temp、cur、newCur；

    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* cur = head;
        ListNode* temp = nullptr;
        ListNode* newCur = nullptr;
        while(cur != nullptr){
            temp = cur->next;
            cur->next = newCur;
            newCur = cur;
            cur = temp;
        }
        return newCur;
    }

方法2：递归

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    if(pHead==NULL || pHead->next==NULL){
        return pHead;
    }
        ListNode* ans = ReverseList(pHead->next);
        //让当前结点的下一个结点的 next 指针指向当前节点
		//同时让当前结点的 next 指针指向NULL ，从而实现从链表尾部开始的局部反转
        //最小递归的情况是321变成123
        pHead->next->next=pHead;
        pHead->next=NULL;
        return ans;
    }
};