每日leetcode

206. 反转链表 - 力扣（LeetCode）

题目

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

示例 1：

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

输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]

输出：[2,1]

示例 3：

输入：head = []

输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 next = pre; if(follow == nullptr) break; pre = head; head = follow; follow = follow->next; } return head; } };

  递归

  /**
   * 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* changeDirection(ListNode* pre, ListNode* follow) {
          ListNode* tmp = follow->next;
          follow->next = pre;
          if(tmp == nullptr) return follow;
          else return changeDirection(follow, tmp);
      }
      ListNode* reverseList(ListNode* head) {
          if(head == nullptr) return nullptr;
          return changeDirection(nullptr, head);
      }
  };

  复杂度分析

  迭代

  • 时间复杂度：至多访问每个节点3次，所以时间复杂度是O(n)的。
  • 空间复杂度：O(1)。

    递归

    • 时间复杂度：O(n)。
    • 空间复杂度：等价于递归的栈空间，即O(n)。

      官方题解（墙裂推荐看看，实现的思路很妙！！！！）

      • 迭代的方法有优化的空间，中间的停步判断其实可以不用额外设计一个follow==nullptr来停步，只要保持维护一个cur指针，每次都将下一个节点存储在一个中间节点中，那么就可以直接通过cur指针是否为空判断是否停步了（甚至不用判断原链表是否为空这步操作了）。
      • 复现：

      • /**
         * 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) {
                ListNode *pre = nullptr, *cur = head;
                while(cur) {
                    ListNode *follow = cur->next;
                    cur->next = pre;
                    pre = cur;
                    cur = follow;
                }
                return pre;
            }
        };

      • 官解的递归总体的思路就是先深入到最后一个节点，然后从最后一个节点开始反转。
      • 首先考虑停步策略，只有当节点为空（本身的输入就是空的情况）或者节点没有后续节点时，到达链表的最尾端。
      • 然后考虑反转的部分，显然是先反转后面的节点，再开始处理当前节点。
      • 那么先往下做一层递归，然后再考虑当层节点的翻转，首先我们需要把后继节点翻转了再翻转前驱节点，否则后继节点将无法通过node->next获得，那么后继节点怎么进行反转呢？
      • 当后继节点为node->next时，若翻转了，其next节点将会变回node，那么我们便可以直接让node->next->next = node来实现后继节点指向当前节点的翻转；
      • 然后再翻转前驱节点，因为每一层的前驱节点的翻转都是有前一节点的后续节点翻转实现的，所以在这里我们可以不做处理。但是因为最后链表头需要指向nullptr，所以为了代码的简洁，我们不妨就将前驱节点全反转为nullptr，那么链表头因为没有前驱节点的递归没有指向nullptr的问题就解决了（amazing！好想法）。
      • 复现：

      • /**
         * 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) {
                if(!head || !head->next) return head;
                ListNode *tail = reverseList(head->next);
                head->next->next = head;
                head->next = nullptr;
                return tail;
            }
        };