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

2025年- H50-Lc158 --25. k个一组翻转链表(链表，双指针，虚拟头节点）--Java版

news 2025/7/13 23:46:42

1.题目描述

在这里插入图片描述

2.思路

链表分区为已翻转部分+待翻转部分+未翻转部分。给一个链表和整数 k，每 k 个一组进行翻转，如果剩下的节点不足 k 个就不翻转。
(1)每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
(2)需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
(3)初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
(4)经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next
翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
(5)特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
时间复杂度为 O(n∗K) 最好的情况为 O(n) 最差的情况未 O(n ^2 )
在这里插入图片描述

补充

3.代码实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(0); // 虚拟头结点，方便处理边界情况dummy.next = head;ListNode pre = dummy; // pre：每组的前一个节点while (head != null) {ListNode end = pre; // 每组的尾部初始化// 看剩下是否有 k 个节点，不够就不翻转for (int i = 0; i < k; i++) {end = end.next;if (end == null) return dummy.next; // 不够 k 个，直接返回}ListNode nextGroupHead = end.next; // 下一组的起点ListNode[] reversed = reverseList(head, end); // 翻转这组链表// reversed[0] 是翻转后的新头，reversed[1] 是新尾head = reversed[0];end = reversed[1];// 重新连接链表pre.next = head;end.next = nextGroupHead;// 为下一轮准备pre = end;head = end.next;}return dummy.next;}// 翻转从 head 到 end 之间的链表，返回 [新头，新尾]public ListNode[] reverseList(ListNode head, ListNode end) {ListNode prev = end.next;ListNode curr = head;while (prev != end) {ListNode nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}return new ListNode[]{end, head}; // 翻转后，end 变成头，head 变成尾}}

方法2：带测试用例。

 class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
public class H25 {public ListNode reverseKGroup(ListNode head, int k) {if (head == null || k <= 1) return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;while (head != null) {ListNode end = pre;// 提前移动 end k 步，如果不足 k 个，直接返回for (int i = 0; i < k; i++) {end = end.next;if (end == null) return dummy.next;}ListNode nextGroupHead = end.next;ListNode[] reversed = reverseList(head, end);ListNode newHead = reversed[0];ListNode newEnd = reversed[1];pre.next = newHead;newEnd.next = nextGroupHead;pre = newEnd;head = nextGroupHead;}return dummy.next;}private ListNode[] reverseList(ListNode start, ListNode end) {ListNode nextGroupHead = end.next; // ✅ 提前缓存，避免循环里访问 end.nextListNode prev = nextGroupHead;ListNode curr = start;while (curr != nextGroupHead) {ListNode nextTmp = curr.next;curr.next = prev;prev = curr;curr = nextTmp;}return new ListNode[]{end, start};  // 翻转后 end 是新的头，start 是新的尾}
public static void main(String[] args)
{H25 test=new H25();ListNode node5=new ListNode(5,null);ListNode node4=new ListNode(4,node5);ListNode node3=new ListNode(3,node4);ListNode node2=new ListNode(2,node3);ListNode head=new ListNode(1,node2);ListNode res=test.reverseKGroup(head,2);System.out.print("输出每k个元素翻转链表的结果： ");while (res != null) {System.out.print(res.val);if (res.next != null) System.out.print(" -> ");res =res.next;}System.out.println();
}
}