【LeetCode刷题记录】92. 反转链表 II & 25. K 个一组翻转链表

两题都是反转链表，放在一起整理。
图解来自B站视频讲解：反转链表（强推！！！）

92 反转链表 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
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

思路

（1）整个链表翻转【LeetCode刷题记录】206. 反转链表：
cur从head开始，用nxt存它本来的下一个节点，pre用于保存当前节点作为下一个节点的前节点。
先用nxt保存它原来的next节点，再更改其next指向为pre
更新pre为cur，更新cur为nxt（顺序不可颠倒）


翻转结束后，pre指向链表末尾，cur指向链表链表末尾的下一个节点。

（2）部分链表翻转：
p0为翻转区间的前一个节点。
翻转区间的翻转过程同上。
注意翻转结束后，更新p0下一个节点的next指向为pre，p0的next指向为cur。


特殊情况：考虑left=1，p0指向谁？
设置哑结点，left=1，p0指向哑结点。

代码

/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* p0 = dummy;
        // p0是反转区间的前一个节点
        for (int i = 0; i < left - 1; i++) {
            p0 = p0->next;
        }
        // 进行反转
        ListNode* pre = nullptr;
        ListNode* cur = p0->next;
        for (int i = 0; i < right - left + 1; i++) {
            ListNode* nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        p0->next->next = cur;
        p0->next = pre;
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

25 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

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

思路

（3）每k个一组翻转链表
不足k个不能翻转，可先求链表长度，翻转k个链表后就将长度-k，不足k个就不翻转。每次翻转的过程与上面的部分链表翻转过程相同。
最后要更新p0的位置，可先用nxt保存下一个p0节点，即nxt = p0->next;p0 = nxt;

代码

/**
 * 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* cur = head;
        int n = 0;
        while (cur) {
            n++;
            cur = cur->next;
        }
        ListNode* dummy = new ListNode(0, head);
        ListNode* p0 = dummy;
        ListNode* pre = nullptr;
        ListNode* nxt;
        // p0是长度为k的链表区间的前一个节点
        cur = p0->next;
        // 剩余长度>=k才可翻转
        while (n >= k) {
            n = n - k;
            // 翻转长度为k的部分链表
            for (int i = 0; i < k; i++) {
                nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }
            // 先把p0的next存下来
            nxt = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            // 更新p0
            p0 = nxt;
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46