题目
给你链表的头节点 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 <= 50000 <= Node.val <= 1000
解题
方法一：模拟 迭代 反转链表
思路
对链表以 k 为长度进行分区处理，具体操作：
遍历链表，记录每个区的头节点(partHead)，以及头节点的前驱节点(beforePart)用以拼接反转后的区链表（由于整个链表的头节点没有前驱节点，所以新建一个假头(dummy)链接整个链表）。
记录当前遍历的节点的后继节点(oriNext)（如果遍历到的节点是区链表的尾节点，要进行反转区链表，导致破坏其中的指向关系）。
当(curr)遍历到每一个区的尾节点时(i % k == 0)：
- 记录当前区链表的头节点(
partHead)用作下一个区链表头节点的前驱节点(partTailAfterReverse)（因为区链表反转后头节点就变成了当前区链表的尾节点，也就是下一个区链表的头节点的前驱节点） - 然后把区头节点(
partHead)及区长度(k)传入反转方法(reversePart())进行反转，该方法返回反转后区链表的头节点 - 把反转后的区链表接入原链表
- 把下一个区链表的头节点(
partHead)初始化为原遍历节点的后继节点(oriNext) - 把下一个区链表的头节点的前驱节点(
beforePart)初始化为当前区链表的尾节点
遍历完成后把长度不够一个区的剩余部分接入原链表即可。
注意返回的是假头的后继节点，因为整个过程中只有假头的指向关系算是没变的。
代码
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// dummy: 假头, beforePart: 区头节点的前驱节点
ListNode dummy = new ListNode(-1, head), beforePart = dummy;
// partHead: 区头节点, curr: 当前遍历到的节点, oriNext: 当前遍历到的节点的后继节点
ListNode partHead = head, curr = head, oriNext;
// 结束条件: 遍历到链表末端, 增量: curr节点向前推
for (int i = 1; curr != null; i++, curr = oriNext) {
// 记录当前遍历的节点的后继节点
// 因为如果遍历到的节点是区链表的尾节点，要进行反转区链表，导致破坏其中的指向关系
oriNext = curr.next;
// 当 curr 遍历到每一个区的尾节点时
if (i % k == 0) {
// 记录当前区链表的头节点用作下一个区链表头节点的前驱节点
// 因为区链表反转后头节点就变成了当前区链表的尾节点 (1)
// 也就是下一个区链表的头节点的前驱节点
ListNode partTailAfterReverse = partHead;
// 把区头节点及区长度传入反转方法进行反转，该方法返回反转后区链表的头节点
// 并把反转后的区链表接入原链表
beforePart.next = reversePart(partHead, k);
// 把下一个区链表的头节点初始化为原遍历节点的后继节点
partHead = oriNext;
// 把下一个区链表的头节点的前驱节点初始化为当前区链表的尾节点 原因如上 (1)
beforePart = partTailAfterReverse;
}
}
// 遍历完成后把长度不够一个区的剩余部分接入原链表
beforePart.next = partHead;
// 注意返回的是假头的后继节点，因为整个过程中只有假头的指向关系算是没变的
return dummy.next;
}
public ListNode reversePart(ListNode head, int len) {
ListNode curr = head, newPrev, newNext = null;
for (int i = 0; i < len; i++) {
newPrev = curr.next;
curr.next = newNext;
newNext = curr;
curr = newPrev;
}
return newNext;
}
}
截断分组结尾反转链表再接回去：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1, head);
ListNode before = dummy, end = dummy;
while (end != null) {
for (int i = 0; i < k && end != null; ++i) end = end.next;
if (end == null) break;
ListNode begin = before.next;
ListNode next = end.next;
end.next = null;
before.next = reverseList(begin);
begin.next = next;
end = before = begin;
}
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode curr = head, newNext = null, newPrev;
while (curr != null) {
newPrev = curr.next;
curr.next = newNext;
newNext = curr;
curr = newPrev;
}
return newNext;
}
}
class Solution {
ListNode* reverseList(ListNode* head) {
ListNode* curr = head, * newNext = nullptr, * newPrev;
while (curr) {
newPrev = curr->next;
curr->next = newNext;
newNext = curr;
curr = newPrev;
}
return newNext;
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1, head);
ListNode* before = dummy, * end = dummy;
while (end) {
for (int i = 0; i < k && end; ++i) end = end->next;
if (!end) break;
ListNode* begin = before->next;
ListNode* next = end->next;
end->next = nullptr;
before->next = reverseList(begin);
begin->next = next;
before = end = begin;
}
return dummy->next;
}
};
评论区