LeetCode25:K个一组翻转链表
leetcode25:K个一组翻转链表
1、题目描述
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例1：
img
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]示例2：
img
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]提示：
- 表中的节点数目为
n。 1<=k<=n<=50000<=Node.val<=1000
2、解题思路
- 只要剩余的结点数量大于
k个，我们就一直执行头插法。 - 新创建一个临时节点
dummy，并赋值dummy.next=head,让head称为它的下一个结点，这样无论链表变成什么样子，我们都可以执行返回return dummy.next。 - 执行头插法，其实每次循环只需要执行k-1次头插法即可。
prev指向需要翻转的前一个结点，也就说把prev所指向的结点当作头插法的头结点，依次执行k-1次头插，循环结束之后，赋值prev=curr，让prev继续指向下一次需要翻转结点的前一个结点，也就是说让prev一直是头插法的头。
这块可能画个示意图比较简单，直接描述会忽略很多细节，不过想法都是一样的。
3、代码实现
单链表节点类
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;
}
//遍历单链表
public static void list(ListNode listNode){
while(listNode!=null){
System.out.print(listNode.val+" ");
listNode=listNode.next;
}
System.out.println();
}
}算法实现：
//leetcode25:K个一组翻转链表
public class LeetCode25 {
public static ListNode reverseKGroup(ListNode head,int k){
ListNode dummy = new ListNode(0, head);
ListNode prev=dummy;
while(true){
//检查剩余节点是否有k个，不足则返回
ListNode last=prev;
for (int i = 0; i < k; i++) {
last=last.next;
if(last==null){
return dummy.next;
}
}
//翻转k个节点(使用类似头插法比较简单)
ListNode curr=prev.next;
ListNode p;
//每次翻转执行k-1次头插
for (int i = 0; i < k - 1; i++) {
p=curr.next;
curr.next=p.next;
p.next=prev.next;
prev.next=p;
}
prev=curr; //prev重新指向下一次需要翻转的前一个结点
}
}
public static void main(String[] args) {
ListNode l1 = new ListNode(1);
ListNode l2 = new ListNode(2);
ListNode l3 = new ListNode(3);
ListNode l4 = new ListNode(4);
ListNode l5 = new ListNode(5);
l1.next=l2;
l2.next=l3;
l3.next=l4;
l4.next=l5;
ListNode listNode = reverseKGroup(l1, 2);
//遍历
ListNode.list(listNode);
}上面我们2个一组翻转单链表，结果如下：
image-20221022091734693
image.png
不过这个我感觉借助栈来实现也是可以的，每次入栈k个再出栈k个就行。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
