题解 | 每K个一组反转链表
import java.util.*;
public class Main {
// 翻转单个链表
public static ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head, next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// K组翻转
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, end = dummy;
while (end.next != null) {
// 找到每组的结束位置
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) break;
// 保存相关节点
ListNode start = pre.next;
ListNode next = end.next;
// 断开当前组
end.next = null;
// 翻转当前组并连接
pre.next = reverseList(start);
start.next = next;
// 移动指针到下一组
pre = end = start;
}
return dummy.next;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读入链表
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
String[] nums = sc.nextLine().split(" ");
for (String num : nums) {
tail.next = new ListNode(Integer.parseInt(num));
tail = tail.next;
}
// 读入k
int k = sc.nextInt();
// 处理并输出结果
ListNode result = reverseKGroup(dummy.next, k);
// 输出结果
while (result != null) {
System.out.print(result.val);
if (result.next != null) System.out.print(" ");
result = result.next;
}
System.out.println();
sc.close();
}
}
