每日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 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

思路

迭代

1. 定义三个点，一个前驱节点，一个中间节点，一个后继节点。
2. 让中间节点指向前驱节点，然后将三个节点后移，直到后继节点到达nullptr。

递归

1. 上一题看递归的时空间开销不如迭代就没看，又跑回去看了一下，总体的思路就是每次就处理两个节点，剩下的节点交给下一次调用来完成。

代码实现

迭代

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