1. 题目

反转一个单链表。

示例:

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

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

2. 迭代求解

image.png
image.png
image.png

  • 注意：

    图中的 **pre 是代码中的 cur ， cur 是代码中的 pre** 

/**
 * 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) {

        // base case
        if (head == nullptr)
            return head;
        else if (head->next == nullptr)
            return head;

        // 初始化
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
};

3. 递归求解

image.png

/**
 * 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) {

        // base case
        if (head == nullptr)
            return head;
        else if (head->next == nullptr)
            return head;

        ListNode* ret = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return ret;
    }
};

不展开解释：
image.png

输入 ListNode* ret= reverse(head->next); 后

image.png

按照定义，这个reverse(head->next)执行完成后，整个链表应该变成了这样：

image.png

执行 head->next->next = head; head->next = nullptr 后

image.png

1、递归函数要有 base case，也就是这句：

if (head.next == null) return head;

意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。
2、当链表递归反转之后，新的头节点是last，而之前的head变成了最后一个节点，别忘了链表的末尾要指向 null：

head.next = null;

理解了这两点后，我们就可以进一步深入了，接下来的问题其实都是在这个算法上的扩展。

4. 总结

  • 做了什么

    使用递归和迭代两种方法实现了 leetcode 206 题——反转链表，详细写了分析过程，还有实现的代码

  • 成果是什么

    1. 明白了 递归** 就是 **循环 的概念
    2. 明白了 递归 是不能够直接用脑袋想的，脑袋没法装那么多个栈，要想递归怎么实现的细节，得在纸上画。
    3. 如果不在纸上画，那么递归只能把过程相同就可以了

  • 意义是什么

    1. 今天的刷题任务完成
    2. 对递归的了解又深入了
    3. 自己还有很多需要学习的