LeetCode hot100——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)额外内存空间的算法解决此问题吗？

题解

/** * 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;//待翻转区间的前驱节点 ListNode end = dummy;//待翻转区间的后继节点 while (end.next != null) { // 移动 end，找到本组末尾 for (int i = 0; i < k && end != null; i++) { end = end.next; } if (end == null) break;//不足k个直接退出 ListNode start = pre.next; // 本组起点 ListNode nextStart = end.next;// 下一组起点，保存 end.next = null; // 断开本组，局部反转 pre.next = reverse(start); // pre接上翻转后的新头 start.next = nextStart; // 原来的start变成本组尾巴，接下一组 pre = start; // 更新前驱为本组尾巴 end = pre; // end重置到新pre，准备下一轮 } return dummy.next; } // 反转链表 private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }

思路

1. 先统计剩余节点，不足 k 个直接结束。
2. 对 k 个节点做局部反转。
3. 维护每组的前驱节点，把上一组尾连接新组头；当前组尾变成下一组的前驱。