题目大意：
K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5
说明：
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=25
解题思路分析：
本题我们可以借助一个Stack来解题。我们从链表头部开始，向Stack中插入k个节点，然后在按顺序pop出来实际上就是将这k个节点翻转了一遍。另外如果stack中元素个数不到k个，顺序保持不变即可。
实现代码：
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next=head;
ListNode lastEnd=dummy;
Stack<ListNode> stack=new Stack<>();
while(head!=null){
ListNode first=head;
while(stack.size()<k&&head!=null){
stack.push(head);
head=head.next;
}
if(stack.size()<k) {
lastEnd.next=first;
break;
}
lastEnd.next=help(stack);
lastEnd=first;
}
return dummy.next;
}
ListNode help(Stack<ListNode> stack){
if(stack.size()==0) return null;
ListNode node = stack.pop();
node.next=help(stack);
return node;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 21.90% of Java online submissions for Reverse Nodes in k-Group.
Memory Usage: 40.3 MB, less than 5.17% of Java online submissions for Reverse Nodes in k-Group.
Kotlin版本实现代码：
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
val dummy = ListNode(0);
dummy.next=head;
var lastEnd = dummy;
var stack=Stack<ListNode>();
var hd = head;
outloop@ while(hd!=null){
var first = hd;
while(stack.size<k&&hd!=null){
stack.push(hd);
hd=hd.next;
}
if(stack.size<k) {
lastEnd.next=first;
break@outloop;
}
lastEnd.next=help(stack);
while(lastEnd.next!=null){
lastEnd=lastEnd.next;
}
}
return dummy.next;
}
fun help(stack: Stack<ListNode>) : ListNode?{
if(stack.size==0) return null;
var node = stack.pop();
node.next=help(stack);
return node;
}本题解法执行时间为180ms。
Runtime: 180 ms, faster than 70.00% of Kotlin online submissions for Reverse Nodes in k-Group.
Memory Usage: 34.6 MB, less than 100.00% of Kotlin online submissions for Reverse Nodes in k-Group.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-25-reverse-nodes-in-k-group-解题思路分析/