题目链接
25. K 个一组翻转链表 - 力扣（LeetCode）
题目解析
算法原理
1> 计算出有多少个结点
2> 计算出我们需要翻转多少组: 结点数/k = 组数
3> 每一组都进行k个数的头插
细节
1>使用newHead来组装反转后的结点组成的链表
2>使用cur指向当前结点, 使用prev,第一次指newHead, 后面每一次都指向上一次反转后的最后一个元素, 也就是tmp指向的结点(prev就相当于每次进行头插的"虚拟头结点"
3>每组我们头插, 都需要一个tmp结点指向我们第一个插入的结点, 便于prev指向"虚拟头结点"第一躺的最后一个元素相当于第二趟的虚拟结点
4>使用next记录cur的下一个元素,方便cur头插后能够找到下一个元素
5> 遍历完之后我们剩下的元素直接使用prev.next = cur进行连接
具体的步骤
1. 求出需要逆序多少组: n
遍历链表, 然后 组数 = n/3 余下不需要逆序: n%3
2. 重复n次, 长度为k的链表的 逆序即可
头插法 : cur 指向需要插入的结点, next指向cur的下一个, 然后我们先创建一个虚拟结点head, 然后让cur.next = head.next , head.next = cur, cur = next, next = cur.next ;
注意: 每次循环, 我们需要记录,插入的第一个位置, 因为后面一组插入的地方就是从这个开始
然后紧接着下一组的插入
当执行到最后, 不足k个元素的开始结点的时候, 我们直接吧cur链接过来即可
代码编写
/*** 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) {// 数有多少个结点int count = 0;ListNode node = head;while (node != null) {count++;node = node.next;}// 计算有多少组int group = count / k; // 组数int yu = count % k;// 余数// 虚拟头结点ListNode newHead = new ListNode();ListNode cur = head;ListNode prev = newHead;// 代替newHead进行行动// 一组一组进行头插while (group-- != 0) {// 标记第一个结点ListNode tmp = cur;for (int i = 0; i < k; i++) {// 需要一个next,记录cur的next, 不然cur找不到下一个在哪ListNode next = cur.next;// 头插cur.next = prev.next;prev.next = cur;cur = next;}// 更新prev = tmp;}// 把剩下的结点丢过来prev.next = cur;return newHead.next;}
}
