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]提示链表中的节点数目为n1 k n 50000 Node.val 1000进阶你可以设计一个只用O(1)额外内存空间的算法解决此问题吗来源25. K 个一组翻转链表 - 力扣LeetCode解题分析方法模拟定义两个指针 a 和 ba 正常遍历b 指向 a - k 的位置即 a 的起始位置用一个变量 times 进行计数当 times k将 a - k 到 a 位置的链表进行反转不会反转可见 JAVA练习291- 反转链表-CSDN博客这里需要注意将 a - k - 1 位置的指针指向 aa - 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; } }