206 反转链表

206. 反转链表 - 力扣（LeetCode）
优质题解：【反转链表】：双指针，递归，妖魔化的双指针 - 反转链表 - 力扣（LeetCode）

题目¶

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

数据结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    }
};

解法：迭代¶

            1 --> 2 --> 3 --> 4 --> 5 --> nullptr
nullptr <-- 1 <-- 2 <-- 3 <-- 4 <-- 5

思考过程

列出输入、输出，进行思考
涉及到局部断链，肯定要保存原始的化学键，优先考虑双指针来保存
当前考虑第一个元素1，因此双指针中的一个肯定指向1，还有一个指向谁？
1. 从结果考虑最好，一个指向了1，另一个只能指向nullptr，而不是2。因为1->next = nullptr
2. 如果1->next=nullptr执行完毕，1-->2的键断裂，因此要事先将2保存下来，即next=2
3. 到这里，1就考虑完了，当前状态nullptr <-- 1、2 --> 3 --> 4 --> 5 --> nullptr
4. 根据双指针的意义，可以知道：curr=1、pre=nullptr（pre表示curr的前一个）
考虑第二个元素2
1. 要将双指针往后位移，即pre=1、curr=2
2. 同样，保存2->next，再挂接2->next=1
3. 发现到这里没有问题，先按照前面的分析（while的中止条件先空着不写），把代码写下来
考虑循环体中止情况
1. 因为循环体内会有curr->next，会访问curr的内存，因此要保证curr!=nullptr
考虑返回值
1. 根据循环体中止情况，可以知道跳出循环体的状态是curr==nullptr，那么pre==5
2. 因此，要返回pre
最后，考虑在边界条件下，此逻辑是否满足，不满足需要再加额外的判断。根据特例逐一考虑即可
1. 空链表，要返回nullptr。根据代码，确实是返回nullptr
2. 1 -> nullptr的情况，要返回1。根据代码，确实是返回1
3. 因此，不需要额外添加条件

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* curr = head;

        while(curr != nullptr) {
            //断链前，要将next保存下来
            auto next = curr->next;
            //逆序，接链
            curr->next = pre;

            //下一个状态
            pre = curr;
            curr = next;
        }

        return pre;
    }
};

解法：递归¶

常规¶

递归相对较容易

先把边界条件写清楚，如果没有把握可以多写一个边界条件，保险些
然后就是递归进入下一个状态就好了，把代码写下
带入例子，检验代码
最后，再从简单到难，逐一考虑特例

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //边界条件
        if(head == nullptr) return head;
        if(head->next == nullptr) return head;

        auto old_head = head;           //先保留旧的head
        head = reverseList(head->next); //翻转后面

        //将old_head挂接在最后
        auto p = head;
        while(p->next != nullptr) { //p有下一个
            p = p->next; //继续位移
        }
        p->next = old_head;        //挂old_head
        old_head->next = nullptr;  //记得old_head的next要置空

        return head;
    }
};

优化¶

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //边界条件
        if(head == nullptr) return head;
        if(head->next == nullptr) return head;

        ListNode* newHead = reverseList(head->next); //转剩下的

        //head->next其实就是，newHead最后一个节点了
        // 无需再遍历一次，直接挂接即可
        head->next->next = head; 
        head->next = nullptr; //记得旧head->next要置空
        return newHead;
    }
};

【时间复杂度】完整遍历了一次链表，O(n)

【空间复杂度】取决于递归调用的所需的栈空间，即调用的最大深度。同样的，需要完整遍历一次链表，即O(n)