LeetCode 「困难」25.K 个一组翻转链表
题目描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 8 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
解答
思路
- 边界条件处理
- 如果链表为空或
K小于等于 1，直接返回原链表 - 如果链表长度小于
K，直接返回原链表
- 翻转
K个节点
- 使用一个指针遍历链表，找到第
K个节点 - 翻转从当前节点到第
K个节点之间的链表 - 保存翻转后的子链表的头节点和尾节点
- 递归或循环处理剩余部分
- 将翻转后的子链表的尾节点连接到下一个子链表的头节点
- 递归或循环处理剩余的链表部分，直到整个链表处理完毕
- 返回结果
Code
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
// 用于翻转从 head 开始的 K 个节点
const reverseKNodes = (head, k) => {
let p = head;
for (let i = 0; i < k; ++i) {
if (!p) return null; // 如果不足 K 个节点，返回 null
p = p.next;
}
let prev = null;
let curr = head;
let next = null;
for (let i = 0; i < k; ++i) {
next = curr.next; // 保存下一个节点
curr.next = prev; // 翻转当前节点
prev = curr; // 移动 prev 到当前节点
curr = next; // 移动 curr 到下一个节点
}
head.next = curr; // 连接翻转后的子链表的尾节点到下一个子链表的头节点
return prev; // 返回翻转后的子链表的头节点
};
var reverseKGroup = function(head, k) {
if (!head || k <= 1) return head;
let newHead = reverseKNodes(head, k);
if (newHead) {
head.next = reverseKGroup(head.next, k); // 递归处理剩余部分
}
return newHead || head; // 如果没有翻转，返回原链表
};
详细解释递归操作：
- 翻转当前组
在 reverseKGroup 函数中，首先调用 reverseKNodes 函数来翻转当前的 K 个节点。这个函数会返回翻转后的子链表的头节点
const newHead = reverseKNodes(head, k);
- 如果
newHead为null，说明当前组的长度不足 K，不需要翻转，直接返回原链表 - 如果
newHead不为null，说明当前组已经成功翻转
- 递归处理下一组
翻转当前组后，需要处理剩余的链表。递归调用 reverseKGroup 处理剩余的链表部分
if (newHead) {
head.next = reverseKGroup(head.next, k);
}
head是翻转后当前组的尾节点（原头节点）reverseKGroup(head.next, k)递归调用处理剩余的链表部分，返回翻转后的下一组链表的头节点- 将当前组的尾节点连接到下一组的头节点
- 返回结果
最后，返回翻转后的链表的头节点
return newHead || head;
- 如果
newHead不为null，返回翻转后的链表的头节点 - 如果
newHead为null，说明当前组没有翻转，返回原链表的头节点