day10 反转链表

不懂一点 ppt。
周五组会汇报读论文情况，我论文也没读完，ppt 也还没有做。

读题

这题标的是简单，希望能尽快完成。
要求很简单：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

---

看上去简单，思路也给出来了。
但肯定对时间复杂度和空间复杂度有点要求，不能随随便便暴力去做。

思路

说是可以迭代递归，但是我打算只使用递归，节约点时间；迭代直接看题解得了。我的思路是创建一个等大的新链表。直觉告诉我肯定有方法可以直接将当前链表转化为反转链表，不开辟新空间，但我一时想不到应该怎么做。
现在，我有 head，节点定义：

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) {}
};

就是之前那一套东西。如果是递归的话，有函数 fun(node)：

• 如果 node->next 为 nullptr：
  • 将 head_new 赋值为当前 node
  • 返回 head_new
• 调用 fun(head->next)，返回值为 node_new
• 对 node_new->next 赋值，为 node
• 返回 node_new->next

指针 node_new 是正向递归时，node 的下一个节点，也就是 node->next；反向回来的时候，node_new->next 就应该是 node 了。至于 val，应该是不需要手动赋值的
于是有代码：

class Solution {
public:
    ListNode* head_new;
    ListNode* fun(ListNode* node){
        if(node==nullptr) return nullptr;
        if(node->next==nullptr){
            head_new = node;
            return head_new;
        }
        ListNode* node_new = fun(node->next);
        node_new->next = node;
        return node_new->next;
    }
    ListNode* reverseList(ListNode* head) {
        if(fun(head)==nullptr) return nullptr;
        return head_new;
    }
};

执行出错了。检查发现应该是原 head（也就是现在的尾巴）的 next 不是 nullptr。修改：

class Solution {
public:
    ListNode* head_new;
    ListNode* fun(ListNode* node){
        if(node->next==nullptr){
            head_new = node;
            return node;
        }
        ListNode* node_new = fun(node->next);
        node_new->next = node; //指针设为node，node指针仍然存在，且可以操作
        node->next = nullptr; //全部设为nullptr
        return node;
    }
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr) return nullptr;
        fun(head);
        return head_new;
    }
};

提交，通过。

结果

0 ms，13.48 MB。内存吃得比较多。
如果是迭代，应该会少吃很多，因为递归是使用了栈来保存返回的指针，如果深度比较深，那么栈就会用得比较大。迭代最少应该只需要三个临时指针。

官方题解

迭代

官方的迭代很优雅，使用了三个指针：

• 前一个节点
• 现在的节点
• 下一个节点

具体做法是在当前指针不为空时：

• 现在的节点的 next 设置为前一指针
• “前一个节点”设置为现在的节点
• “现在的节点”设置为“现在的节点”的 next 指针原本指向的节点

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

这么看来，这题是完全没有必要使用递归。

递归

官方代码也很优雅，看来是我的问题。
官方没有使用新函数，而是直接是 reverseList。也没有使用全局变量。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

太优雅了。

收获

1. 复习了递归
2. 明白了迭代也能很优雅
3. 明白了递归不一定要新建函数