JAVA练习299- K 个一组翻转链表

题目概览

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

进阶：你可以设计一个只用O(1)额外内存空间的算法解决此问题吗？

来源：25. K 个一组翻转链表 - 力扣（LeetCode）

解题分析

方法：模拟

定义两个指针 a 和 b，a 正常遍历，b 指向 a - k 的位置（即 a 的起始位置），用一个变量 times 进行计数，当 times == k，将 a - k 到 a 位置的链表进行反转（不会反转可见 JAVA练习291- 反转链表-CSDN博客），这里需要注意将 a - k - 1 位置的指针指向 a，a - k 位置指针指向 a + 1，然后 times 清零，b 指向当前位置，a 继续遍历即可。

时间复杂度：O(n)
空间复杂度：O(1)

/** * 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 a = new ListNode(), b = head, result = null; a.next = head; int times = 1; while(b != null) { if (times < k) { b = b.next; times++; } else { ListNode tempB = b.next; ListNode tempA = a.next; reverse(a, a.next, b.next); a = tempA; times = 1; if (result == null) { result = b; } b = tempB; } } return result; } private void print(ListNode a) { StringBuilder sb = new StringBuilder(); while(a != null) { sb.append(a.val); sb.append(","); a = a.next; } System.out.println(sb.toString()); } private void reverse(ListNode preA, ListNode a, ListNode b) { ListNode cur = a, pre = b; while(cur != b) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } preA.next = pre; } }