1.反转链表

题目描述

给你单链表的头节点 $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

（迭代法）$O(n)$

• 反转链表即将所有节点的$next$指针指向前驱节点。由于是单链表没有前驱指针，因此我们需要维护一个额外的指针保存前驱，同时在改变当前节点的$next$指针前，不要忘记保存他的后继节点。
• 时空复杂度：时间复杂度$O(n)$空间复复杂度$O(1)$

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *cur = head;while (cur) {ListNode *next = cur->next;cur->next = prev;prev = cur, cur = next;}return prev;}
};

解法2

（递归法）$O(n)$

• 这里是一个难点，首先我们先考虑 $reverseList$ 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
• 所以我们可以先递归处理reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点$tail$，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是$tail$。
• 对于样例1 2 3 4 5,我们从2为头节点开始递归，调用reverseList() 得到5 4 3 2。但此时的链表并非是1 5 4 3 2,此时的链表是1->2和5 4 3 2两部分，也就是头节点1依然指向2,要想访问到2，使用head->next即可。这时我们将2指向1，让1指向nullptr即可实现整个链表的反转。如下图
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(n)$
  

/**  * Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
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;}
};

解法3

• 栈维护实现反转
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(n)$

/**  * Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {stack<ListNode*> st;while (head) {st.push(head);head = head->next;}ListNode *dummy = new ListNode(-1);ListNode *p = dummy;while (!st.empty()) {ListNode *node = st.top();st.pop();node->next = nullptr;p->next = node;p = p->next;}return dummy->next;}
};

2.反转链表 II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。

示例 1：

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

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点的数目为$n$
• $-500<=Node.val<=500$
• 进阶：你可以使用一趟扫描完成反转吗？

解法1

• 一个很直观的做法便是我们把这三部分分别截取出来再将中间部分反转，最后连接即可
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(1)$

class Solution {
public:void reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *cur = head;while (cur) {ListNode *next = cur->next;cur->next = prev;prev = cur, cur = next;}}ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode *dummy = new ListNode(-1); // 设置哨兵节点 避免left=1时的讨论dummy->next = head; // 关键修复：连接虚拟头节点到原链表ListNode *p = dummy;// 移动p到left位置的前一个节点for (int i = 0; i < left - 1; i++) {p = p->next;}// 走 right - left + 1步 来到right节点ListNode *rightNode = p;for (int i = 0; i < right - left + 1; i++) {rightNode = rightNode->next;}// 截取链表ListNode *leftNode = p->next;ListNode *curr = rightNode->next;// 切断连接p->next = nullptr;rightNode->next = nullptr;// 反转中间部分链表reverseList(leftNode);// 重新连接链表p->next = rightNode; leftNode->next = curr; return dummy->next;}
};

解法2

思路

• 举个例子：对于示例1，链表为1 2 3 4 5要求我们反转中间的2 3 4部分，我们要先找到2的前驱节点即将指针移动left-1次，然后再对中间长度为right - left + 1的链表进行反转操作，由于上面的反转链表1我们知道将其反转为4 3 2,此时pre指向4,而p->next指向的节点为2,cur为后半部分链表，因此我们执行p->next->next = cur, p->next = pre
• 注意left = 1时候我们可以添加一个哨兵节点避免空指针
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(1)$
• 如下图所示（摘自灵神题解）

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode *dummy = new ListNode(-1); // 设置哨兵节点 避免left=1时的讨论dummy->next = head; // 关键修复：连接虚拟头节点到原链表ListNode *p = dummy;// 移动p到left位置的前一个节点for (int i = 0; i < left - 1; i++) {p = p->next;}// 反转中间部分 [left, right]ListNode *pre = nullptr;ListNode *cur = p->next;for (int i = 0; i < right - left + 1; i++) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}// 重新连接链表// 注意必须先执行第一句p->next->next = cur; // 反转后的尾节点接剩余链表p->next = pre;       // 前半部分接反转后的头节点return dummy->next;}
};

3. K 个一组翻转链表

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

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

示例 2：

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

提示：

• 链表中节点的数目为$n$
• $1<=k<=n<=5000$
• $0<=Node.val<=1000$
• 进阶：你可以使用一趟扫描完成反转吗？

解法1

思路

• 题目要求我们将链表k个一组反转，小于k的不反转，对于每一组的内部反转，同反转链表I，重要的是在反转后每个部分的重新连接，这里同反转链表II
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(1)$

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int n = 0;// 求表长for (ListNode* cur = head; cur; cur = cur->next) {n ++;}ListNode *dummy = new ListNode(-1);dummy->next = head;ListNode *p0 = dummy;ListNode *pre = nullptr;ListNode *cur = head;while (n >= k) { // k个一组反转n -= k;// 同迭代版 反转链表for (int i = 0; i < k; i++) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}// 与后面的合并ListNode *nxt = p0->next; // 要保存p0->nextnxt->next = cur;p0->next = pre;p0 = nxt;}return dummy->next;}
};

解法2

思路

• 递归实现，把每个组看作一个子问题，递归调用
• 时空复杂度：时间复杂度$O(n)$ 空间复复杂度$O(n)$

/*** 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* reverseKGroup(ListNode* head, int k) {ListNode *p0 = head;for (int i = 0; i < k; i++) { if (!p0) return head; // 不够k个不反转p0 = p0->next;}// 反转链表ListNode *pre = nullptr;ListNode *cur = head;for (int i = 0; i < k; i++) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}// 检索下一组head->next = reverseKGroup(cur, k);return pre;}
};

参考

• 灵神题解-反转链表【基础算法精讲 06】
• 【25. K 个一组翻转链表】C++ 解法：「递归」