每k个节点一组反转链表

系列文章目录

一、思路

每k个节点一组反转链表，最后节点不足k个的，保持不变
例如：

输入：1->2->3->4->5->6->7，k = 3
输出：3->2->1->6->5->4->7

思路：
使用虚拟头节点方便操作
每次处理一组k个节点
反转当前组内的节点
将反转后的组连接到前一部分
重复处理

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 虚拟头节点ListNode dummy = new ListNode(0);dummy.next = head;// prev 是当前组的前一个节点ListNode prev = dummy;while (true) {// 检查是否还有 k 个节点ListNode curr = prev.next;int count = 0;while (count < k && curr != null) {curr = curr.next;count++;}if (count < k) break; // 不足 k 个，停止// 反转当前组：从 prev.next 到 curr - 1ListNode first = prev.next;ListNode last = prev.next;for (int i = 0; i < k - 1; i++) {last = last.next;}// 反转区间 [first, last]ListNode nextGroup = last.next;ListNode prevNode = prev;ListNode currNode = first;// 反转 k 个节点for (int i = 0; i < k; i++) {ListNode next = currNode.next;currNode.next = prevNode;prevNode = currNode;currNode = next;}// 连接反转后的组prev.next = prevNode;first.next = nextGroup;// 更新 prev 为当前组的最后一个节点（即原来的第一个节点）prev = first;}return dummy.next;}// 测试代码public static void main(String[] args) {// 构建链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7ListNode node1 = new ListNode(1);node1.next = new ListNode(2);node1.next.next = new ListNode(3);node1.next.next.next = new ListNode(4);node1.next.next.next.next = new ListNode(5);node1.next.next.next.next.next = new ListNode(6);node1.next.next.next.next.next.next = new ListNode(7);Solution solution = new Solution();ListNode result = solution.reverseKGroup(node1, 3);// 打印结果while (result != null) {System.out.print(result.val + " ");result = result.next;}}
}