方法一：迭代

• 先创建一个pre和一个cur的ListNode变量；
• 然后迭代遍历链表，然后反转指针指向。

复杂度

• 时间复杂度为O（N）；
• 空间复杂度为O（1）。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;

        while(cur!=NULL)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

方法二：递归

• 先判断指针和next指针是否为NULL，如果是就返回该指针；
• 将当前指针的next指针作为参数继续递归；
• 将当前指针的下一个指针的next指向当前指针；
• 之后让当前节点的next指针指向NULL，实现从链表尾部开始的局部反转；
• 最后返回结果。

复杂度

• 时间复杂度为O（N）；
• 空间复杂度为O（N），递归栈。

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
        {
            return head;
        }

        ListNode* res = ReverseList(head->next);
        head->next->next = head; // 反转指针

        head->next = NULL; // 让当前节点的next指针指向NULL,实现从链表尾部开始的局部反转
        return res;
    }
};