题解 | #反转链表#

第一种方法：利用双指针迭代求解

时间复杂度为：o(n)

空间复杂度为：o(1)

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(head == nullptr)
            return nullptr;
        
        while(head != nullptr) {
            pNext = head->next;
            head->next = pTemp;
            pTemp = head;
            head = pNext;
        }
        return pTemp;
    }
private:
    ListNode* pTemp = nullptr;
    ListNode* pNext = nullptr;
};

第二种方法：使用递归求解

时间复杂度为：o(n)

空间复杂度为：o(n)

class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
         if(head == nullptr || head->next == nullptr)
            return head;
        //反转下一个
        ListNode* newHead = ReverseList(head->next);
        //逆转本级节点
        head->next->next = head;
        //尾部设置空节点
        head->next = nullptr;
        return newHead;
    }
};

第三种方法：利用栈来求解

时间复杂度为：o(n)

空间复杂度为：o(n)

不符合题目的要求，但也提供出来开阔视野

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

        while (p!= nullptr) {//将链表元素入栈
            sk.push(p) ;
            p = p->next;
        }

        newhead = sk.top();
        sk.pop ();
        temp = newhead;
        while (!sk.empty()) {
            temp->next = sk.top();
            temp = temp->next;
            sk.pop ();
        }
        temp->next = nullptr;
        return newhead;
    }
private:
    stack<ListNode*> sk;
    ListNode* p;
    ListNode* newhead;
    ListNode* temp;
};