招聘网站开发流程,私密浏览器下载,建筑人才评价网,网站扁平化K 个一组翻转链表
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改…K 个一组翻转链表
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
示例1 输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5]
解题思路
1、这个问题可以通过迭代的方式来实现遍历链表并每 k 个节点一组进行翻转。2、需要注意的是我们需要记录每个翻转段的起始节点和结束节点以便连接上一段和下一段。
具体步骤 1、定义一个辅助的虚拟头节点 dummyHead指向链表的头部。 2、初始化两个指针 start 和 end分别表示每个翻转段的起始和结束节点。 3、使用一个循环每次迭代对当前翻转段进行翻转。在循环中 1计算当前翻转段的长度是否达到 k。如果不足 k则直接返回结果因为剩余的节点不需要翻转。 2 对当前翻转段进行翻转。翻转后将翻转段的起始节点翻转后的最后一个节点连接到上一个翻转段的结束节点将翻转后的最后一个节点翻转前的起始节点连接到下一个翻转段的起始节点。 3更新 start 和 end 指针继续下一段的翻转。
Java实现
public class ReverseKGroup {static class ListNode {int val;ListNode next;ListNode(int x) {val x;next null;}}public ListNode reverseKGroup(ListNode head, int k) {ListNode dummyHead new ListNode(0);dummyHead.next head;//每一段的起始和结束节点ListNode start dummyHead;ListNode end dummyHead;while (end.next ! null) {// 计算当前翻转段的长度for (int i 0; i k end ! null; i) {end end.next;}// 如果当前翻转段长度不足 k直接返回if (end null) {break;}// 记录翻转段的起始节点和下一段的起始节点ListNode nextSegment end.next;ListNode segmentStart start.next;// 断开当前翻转段与下一段的连接end.next null;// 翻转当前翻转段start.next reverseList(segmentStart);// 将翻转后的最后一个节点连接到下一段的起始节点segmentStart.next nextSegment;// 更新 start 和 end 指针为下一段的起始节点//注意边界值这里是用的第一段的末节点segmentStart。//不是用的下一段的起点因为一开始我们用的是dummyHead而不是用的head//在for循环中 i 0开始的start segmentStart;end segmentStart;}return dummyHead.next;}private ListNode reverseList(ListNode head) {ListNode prev null;ListNode current head;while (current ! null) {ListNode nextNode current.next;current.next prev;prev current;current nextNode;}return prev;}public static void main(String[] args) {// 构造链表 1 - 2 - 3 - 4 - 5-6-7ListNode head new ListNode(1);head.next new ListNode(2);head.next.next new ListNode(3);head.next.next.next new ListNode(4);head.next.next.next.next new ListNode(5);head.next.next.next.next.next new ListNode(6);head.next.next.next.next.next.next new ListNode(7);int k 3;// 调用 reverseKGroup 方法翻转链表ReverseKGroup solution new ReverseKGroup();ListNode result solution.reverseKGroup(head, k);// 打印翻转后的链表while (result ! null) {System.out.print(result.val );result result.next;}// 输出2 - 1 - 4 - 3 - 5}
}
时间空间复杂度
时间复杂度O(n)其中 n 是链表的长度需要遍历一次链表。空间复杂度O(1)只需要使用常数级别的额外空间
