我们做一下反转链表的习题206：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]
看一下灵神的代码：方法一：递归（尾插法）
递归递归，有递有归。

我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。

新链表的末尾节点在哪？就是当前节点的 next。具体实现如下。

class Solution:
    # 首先「递」到链表末尾，把末尾节点作为新链表的头节点 rev_head
    # 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 判断 head is None 是为了兼容一开始链表就是空的情况
        if head is None or head.next is None:
            return head  # 链表末尾，即下面的 rev_head
        rev_head = self.reverseList(head.next)  # 「递」到链表末尾，拿到新链表的头节点
        tail = head.next  # 在「归」的过程中，head.next 就是新链表的末尾
        tail.next = head  # 把 head 插在新链表的末尾
        head.next = None  # 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
        return rev_head
答疑
问：为什么不写 head.next = null 的代码，会提示「超出内存限制」？这应该是超时呀？

答：这和力扣的判题机制有关，评测机会先把链表转成字符串，再去比对答案。这会遍历链表，如果链表有环，生成的字符串会无限延长，在超时之前就超出内存限制了。

复杂度分析
时间复杂度：O(n)，其中 n 为链表节点个数。
空间复杂度：O(n)。递归需要 O(n) 的栈空间。
方法二：迭代（头插法）
视频讲解：【基础算法精讲 06】，制作不易，欢迎点赞~

简单理解：比如链表为 1→2→3。创建一个新的空链表，然后用头插法依次把节点 1,2,3 插到这个新链表的头部，就得到了链表 3→2→1，这正是反转后的链表。

头插法的意思是，把一个节点 node 指向链表头节点（node.next 更新为链表头节点），那么 node 就插在了链表的左侧，新链表的头节点为 node。

对于链表 1→2→3，结合代码来说，顺序为：

第一轮循环结束后，得到链表 1。
第二轮循环结束后，得到链表 2→1。
第三轮循环结束后，得到链表 3→2→1。
注：代码每轮循环结束后，pre 表示最新得到的链表。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre  # 把 cur 插在 pre 链表的前面（头插法）
            pre = cur
            cur = nxt
        return pre
复杂度分析
时间复杂度：O(n)，其中 n 为链表节点个数。
空间复杂度：O(1)。

c语言实现：一些错误
1. node没有初始化
2. 没保存val
3. 只执行一次
4. 没有循环处理整个链表
5. pre->next = node->next逻辑错误
//这里是创建了新节点
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* header =
        malloc(sizeof(struct ListNode));

    header->next = NULL;

    while(head != NULL)
    {
        struct ListNode* node =
            malloc(sizeof(struct ListNode));

        node->val = head->val;

        node->next = header->next;

        header->next = node;

        head = head->next;
    }
    struct ListNode* ans = header->next;
//指向空节点的下一个
    free(header);

    return ans;
}

使用栈的思路：
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* newHead = NULL;
//newhead作为定位指针，当后续节点相连的时候指向当前的最前面的节点
    while(head != NULL)
    {
        struct ListNode* node =
            malloc(sizeof(struct ListNode));

        node->val = head->val;

        node->next = newHead;

        newHead = node;

        head = head->next;
    }

    return newHead;
}
递归的思路：
struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* newHead =
        reverseList(head->next);

    head->next->next = head;

    head->next = NULL;

    return newHead;
}
reverseList(head)=把head后面的链表先反转
然后把head接到最后面

例如：reverseList(1)=reverseList(2)+把1接到最后

而：
reverseList(2)=reverseList(3)+把2接到最后

最终：

3

↓

3 -> 2

↓

3 -> 2 -> 1