当前位置：首页 > news >正文

LeetCode25:K个一组翻转链表

news 2025/2/21 3:07:10

原题地址：. - 力扣（LeetCode）

题目描述

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

实现思路

定义节点：使用ListNode类表示链表节点。

设置虚拟头节点：使用一个虚拟头节点（hair）来处理链表的头部，使得处理操作更加简洁。

遍历链表：使用一个指针head从链表头部开始遍历，找到每一组k个节点：

通过一个循环检查剩余的节点是否至少有k个。
如果不足k个，返回结果（即未变更的链表部分）。

反转k个节点：使用myReverse方法反转找到的k个节点：

该方法接收头节点和尾节点，并逐步将节点的指向反转，最终返回新的头和尾。

重新链接链表：将反转后的子链表连接回原链表：

更新pre.next指向反转后的头节点。
更新反转后的尾节点指向接下来的节点。

更新指针：继续循环，更新pre和head以处理下一个k个节点。

源码实现

class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 创建一个虚拟头节点，简化边界处理ListNode hair = new ListNode(0);hair.next = head; // 虚拟节点指向原链表的头ListNode pre = hair; // 用于连接反转后的链表// 遍历链表while (head != null) {ListNode tail = pre; // 每次从pre开始// 检查剩余部分长度是否大于等于 kfor (int i = 0; i < k; ++i) {tail = tail.next; // 移动tail指针if (tail == null) {return hair.next; // 如果不足k个，直接返回}}ListNode nex = tail.next; // 记录下一部分的起始节点// 反转k个节点ListNode[] reverse = myReverse(head, tail);head = reverse[0]; // 新的头节点tail = reverse[1]; // 新的尾节点// 将反转后的子链表接回原链表pre.next = head; // pre指向新的头节点tail.next = nex; // 新尾节点指向下一部分的起始节点pre = tail; // 更新prehead = tail.next; // 更新head指向下一组}return hair.next; // 返回新链表的头}// 反转链表的方法，返回新的头和尾public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev = tail.next; // prev指向tail的下一个ListNode p = head; // p用于遍历反转// 逐步反转节点while (prev != tail) {ListNode nex = p.next; // 记录下一个节点p.next = prev; // 反转当前节点prev = p; // prev移动到当前节点p = nex; // p移动到下一个节点}return new ListNode[]{tail, head}; // 返回新的尾和头}
}