leetcode：206. 反转链表

题目

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

示例 1：
[简单] 206. 反转链表 - 图1

  1. 输入：head = [1,2,3,4,5]
  2. 输出：[5,4,3,2,1]

示例 2：
[简单] 206. 反转链表 - 图2

  1. 输入：head = [1,2]
  2. 输出：[2,1]

示例 3：

  1. 输入：head = []
  2. 输出：[]

解答 & 代码

解法一：迭代法

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         ListNode* pre = nullptr;    // 前一个节点
  15.         ListNode* cur = head;        // 当前节点
  16.         // 遍历链表，反转
  17.         while(cur != nullptr)
  18.         {
  19.             ListNode* next = cur->next;        // 记录下一个节点
  20.             cur->next = pre;                // 将当前节点的 next 指向前一个节点
  21.             pre = cur;                        // 前一个节点 pre 右移
  22.             cur = next;                        // 当前节点 cur 右移
  23.         }
  24.         return pre;        // 返回反转后的头节点
  25.     }
  26. };

复杂度分析：设链表节点数为 N

  • 时间复杂度 O(N)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 94.42% 的用户
  4. 内存消耗：8 MB, 在所有 C++ 提交中击败了 90.84% 的用户

解法二：递归

递归链表和递归二叉树其实本质是一样的，以递归处理 next 节点这一语句为分界线，

  • 之前的位置是正序位置（进入当前节点），可用于正序输出链表节点；
  • 之后的位置是逆序位置（离开当前节点），可用于逆序输出链表节点。

本题的递归解法类似于动态规划的思想，将当前的大问题分解为子问题。

  • 递归函数定义：输入一个节点 head，将以 head 为头节点的链表反转，并返回反转后的头节点
  • 分解为子问题：递归将以 head->next 为头节点的链表反转，并返回反转后的头节点，即为 last
  • 将当前节点接到 last 链表的尾部，就完成了对以 head 为头节点的链表反转
    • 如何定位到 last 链表的最后一个节点：head->next 是 last 链表反转前的头节点，也就是反转后的尾节点，因此，令 head->next->next = head 即可将 head 节点拼接到尾部
  • 当然，由于当前节点 head 是反转后的最后一个节点，因此需要将 head->next 设为 nullptr

  • 返回反转后链表的头节点 last

    1. /**
    2. * Definition for singly-linked list.
    3. * struct ListNode {
    4. *     int val;
    5. *     ListNode *next;
    6. *     ListNode() : val(0), next(nullptr) {}
    7. *     ListNode(int x) : val(x), next(nullptr) {}
    8. *     ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. * };
    10. */
    11. class Solution {
    12. public:
    13.   // 递归函数定义：输入一个节点 head，将以 head 为头节点的链表反转，并返回反转后的头节点
    14.   ListNode* reverseList(ListNode* head) {
    15.       // 递归结束条件
    16.       if(head == nullptr || head->next == nullptr)
    17.           return head;
    19.       // 递归将以 head->next 为头节点的链表反转，并返回反转后的头节点，记为 last
    20.       ListNode* last = reverseList(head->next);
    22.       // 将当前节点 head 接到 last 链表的尾部
    23.       head->next->next = head;
    24.       // 当前节点 head 是反转后的最后一个节点，因此需要将 head->next 设为 nullptr
    25.       head->next = nullptr;
    26.       // 返回 head 链表反转后的头节点
    27.       return last;
    28.   }
    29. };

    复杂度分析：设链表节点数为 N

  • 时间复杂度 O(N)

  • 空间复杂度 O(N)：递归栈空间复杂度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 94.42% 的用户
  4. 内存消耗：8.2 MB, 在所有 C++ 提交中击败了 22.11% 的用户