这是《剑指Offer》书中的第 24 题：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。链表节点与函数的定义如下：
struct ListNode { int m_nKey; ListNode *m_pNext; };

这道题并不难，这里，我们除了会给出书中的解法外，还会给出一种递归的解法，这也是书中要求思考的解法。

在我们之前的文章中也提到过，解决问题一般有两种思路。一种是自上而下，通常适用于递归；另一种是自下而上， 适用于循环或者动态规划。关于这道题，书中给出的解法是后者，也就是自下而上的方法。

所谓自下而上，则是说从第一个节点开始，逐个节点的将链表反转。要实现这个，我们首先应该有一个指针 node 指向 当前节点，还有一个指针 preNode 指向它的前一个节点。然后，让 node->m_pNext = preNode。但是因为此时 node->m_pNext 已经被赋予了新的值，导致 node 无法向前遍历，所以我们除了要有上述的两个指针外，还需要有一个指针 nextNode 把 node->m_pNext 的值提前保存下来 ，方便 node 继续向前遍历。

所以我们的算法可以描述为：

  • 如果链表是空，则返回 NULL
  • 如果链表只有一个节点，则返回该节点
  • 定义 preNode = NULL, node = head, nextNode = head->m_pNext
  • 进入循环，条件为 1 （无限循环）
    • node->m_pNext = preNode
    • node = nextNode，如果 node 为空，则退出循环
    • nextNode = nextNode->m_pNext
  • 返回 preNode

因为这个方法只需要遍历一次链表就可以实现反转的功能，所以它的时间复杂度为 O(n)；又因为它并不需要额外的 空间，所以它的空间复杂度为 O(1)。

这是我的提交记录。

在介绍完常规解法之后，我们再来看递归解法。递归解法的好处在于它可以将问题简单化，在解决问题的时候 更加容易形成清晰的思路；缺点就是有可能导致重复计算，以及栈调用占用的空间过多。

这道题，我首先想到的就是，要反转链表，我们可以用栈，因为栈的特点是“先进后出”，把一个链表从头节点开始 压入栈中，然后再逐个出栈，就会得到原链表的反转。然后我又想，如果用栈可以解决，那么用递归也可以解决，因为 递归本质上就是栈。于是我就开始思考如何利用递归来完成这个题目。

我们只所以用栈，是因为我们需要知道链表的尾节点，也就是 node->m_pNext == NULL 的节点。所以我们的递归的 base condition 就应该是，如果当前的节点是尾节点，那么就把它返回。然后我们来看如何进行递归调用。我们从尾节点开始考虑，如果我们现在 是倒数第二个节点，现在通过递归调用得到了尾节点，那么我们应该把尾节点 tailNode 的 m_pNext 指向当前节点，即 tailNode->m_pNext = node， 对不对？然后干嘛，将当前节点 node 返回。这样，我们的递归调用函数就写好了。

值得注意的是，我们递归函数最后返回的节点还是头节点 head，此时它已经是反转之后的尾节点了，因此我们还需要将它的 m_pNext 赋为 NULL。 题目中要求我们应该将反转后的头节点返回，所以我们在进行递归调用前，应该先找到原链表的尾节点并保存下来，等递归调用完成之后，我们 再将它返回。

这个方法，因为它需要遍历整个链表去找尾节点，并且还需要通过递归的方式再找一遍尾节点，因此整体的时间复杂度为 O(n)；又因为 它需要 n 个栈空间的函数调用，所以空间复杂度为 O(n)。

这是我的提交记录。

最后，这道题再次向我们强调了，在处理链表问题的时候，我们要对多种情况进行考虑：

  • 空链表
  • 单节点链表
  • 头节点，中间节点，尾节点的处理

以上。