题目的主要信息：

• 给定一个长度为$nn$的链表，反转该链表，输出表头
• 要求：时间复杂度为$O(n)O(n)$，空间复杂度为$O(1)O(1)$

方法一：递归（能过，空间不符合要求）

具体做法：

我们可以利用递归的反向工作来实现逆转。对于每个结点我们递归向下遍历到最后，然后往上依次逆转两个结点，递归终止就是后面遇到了空结点。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL)
            return pHead;
        ListNode* newHead = ReverseList(pHead->next); //反转下一个
        pHead->next->next = pHead; //逆转
        pHead->next = NULL; //设置空结点
        return newHead;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，相当于递归遍历链表
• 空间复杂度：$O(n)O(n)$，递归栈深度为链表长度$nn$

方法二：迭代

具体做法：

我们可以设置两个指针，一个当前结点的指针，一个上一个结点的指针，我们遍历链表的时候，断开当前结点与后面的结点，并用临时变量记录后一个结点，然后当前结点指向上一个结点，再轮换当前指针与上一个指针。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL)
            return NULL;
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while(cur != NULL){
            ListNode* temp = cur->next; //断开链表，要记录后续一个
            cur->next = pre; //当前的next指向前一个
            pre = cur; //前一个更新为当前
            cur = temp; //当前更新为刚刚记录的后一个
        }
        return pre;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历链表一次
• 空间复杂度：$O(1)O(1)$，无额外空间使用