【leetcode】【剑指offer Ⅱ】024. 反转链表

问题描述：

• 给定单链表的头节点 head，反转链表并返回反转后的链表的头节点。

核心思路：

• 该题很有代表性，其可以写出原地反转链表的递归和迭代两个版本的解法。

• 迭代版本的解法相当于是从头到尾遍历链表并模拟断链并反转的过程。

  • 迭代版本解法的步骤如下：
    1. 初始化三个指针 pre、cur 和 next，其中 cur 初始化为 head，另两个指针初始化为空指针。
    2. 只要 cur 不为空，则一直进行下述操作：
       1. 将 next 置为 cur 的下一个节点，即 next = cur->next。【保存下一个节点，因为准备断开 cur 指向 cur->next 的链】
       2. 将 cur 的下个节点置为 pre，即 cur->next = pre。【将 cur 的方向反转】
       3. pre 置为 cur，即 pre = cur。【pre 向后移动】
       4. cur 置为 next，即 cur = next。【cur 向后移动】
    3. 退出循环后，返回 pre 指针作为反转后的链表头部。
  • 可以从例子中理解循环中的四个步骤：

    • 第一步，保存下一个节点：
      

    • 第二步，将 cur 的方向反转：
      

    • 第三步，pre 向后移动：
      

    • 第四步，cur 向后移动：
      

• 由前面可以看出，迭代解法相当于从前往后反转链表，而递归解法相反，是从后往前反转链表。

  • 普通递归版本解法的步骤如下：
    1. 判断 head 非空且 head->next 非空，如果其中一个为空则直接返回 head。【遇到链表的尾部才会在此处直接返回】
    2. 递归调用自身，其参数为 head->next，并将返回结果置为 newHead。【newHead 是本次函数返回的结果，不难想象得出，函数一路递归遍历链表，最后会把链表尾部元素返回作为反转后的链表头部】
    3. 将 head->next 的下一个节点置为 head，即 head->next->next = head。【将 head->next 的方向反转】
    4. 将 head 的下一个节点置为空，即 head->next = nullptr。【此步较为关键，如果不置空，则会造成 cur 与 cur->next 互指的情况】
    5. 最后返回 newHead 指针作为反转后的链表头部。
  • 普通递归都可以进行尾递归优化。
    • 尾递归写法仍然是递归方式的一种，但相比普通递归，其在递归栈的空间上更为节省。
    • 简单地说，尾递归的写法就是将普通递归的内部变量转为函数的参数，而尾递归的最后一步为调用自身。【在此不展开讲解尾递归，SICP 书中有详细介绍】
    • 神奇的地方在于，尾递归优化的解法与迭代解法是一致的，均是从前往后反转链表。

代码实现：

• 双指针迭代解法的代码实现如下：

  class Solution
  {
  public:
      ListNode* reverseList(ListNode* head)
      {
          ListNode* pre = nullptr;
          ListNode* cur = head;
          ListNode* next;
          while(cur)
          {
              next = cur->next;
              cur->next = pre;
              pre = cur;
              cur = next;
          }
          return pre;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

• 单指针迭代解法的代码实现如下：【实质上和前一种解法一致，代码贴自评论区】

  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          ListNode *p;
          for(p=NULL; head; swap(head,p))
              swap(p,head->next);
          return p;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9

• 普通递归解法的代码实现如下：【贴自官方题解】

  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
  4
  5
  6
  7
  8
  9
  10
  11
  12

• 尾递归解法的代码实现如下：

  class Solution
  {
  private:
      ListNode* reverse(ListNode* pre, ListNode* cur) // 尾递归
      {
          if(!cur) return pre;
          ListNode* next = cur->next;
          cur->next = pre;
          return reverse(cur, next); // 最后一步调用自身
      }
  public:
      ListNode* reverseList(ListNode* head)
      {
          return reverse(nullptr, head);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16