流量套餐网站,php是做网站还是网页,汽车网站开发方案,工信部icp备案是什么意思题目描述
力扣原文链接
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。
k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。
你不能只…题目描述
力扣原文链接
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 提示
链表中的节点数目为 n1 k n 50000 Node.val 1000
进阶 你可以设计一个只用 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) {// here is your code }
}解题过程
解题思路
拿到的题目以后应该尽量根据已知条件、函数的入参和返回值抓住变与不变的量、考虑边界条件、加之常用算法手段如递归、迭代、双指针、回溯、分治、动态规划等等从而创造一条完整链路再考虑时间复杂度和空间复杂度的限制问题得解。
回到本题函数入参是一个自定义的ListNode以及指定的小于ListNode长度的正整数用以翻转子链表最终将新链表返回。所以核心问题有两点
函数入参指定的链表是否存在一个或者多个长度为K的子链表如果存在长度为K的子链表如何实现这个不断重复的翻转子链表的工作
接下来把代码要实现的逻辑完整地梳理一遍 针对以上的两个问题我们最少要进行一次O(n) 时间复杂度的链表遍历来确定是否存在合理值K。如果不存在直接返回原链表因为无需翻转。这是最简单的情况。如果存在合理值K那么怎么在O(1)空间复杂度的情况下保证子链表的翻转以及翻转后与旧链表首尾节点的组装 用一个简单实例说明 假设链表为 1 - 2 - 3 K 2那么自然会脱口而出2 - 1 - 3这样看起来是不是很简单呢 实际上处理过程同上面分析的一样先判断是否含有K长度子链表链表长度为3K为2当然符合条件再把K长度子链表 1 - 2 翻转成 2 - 1问题得以解决。
增加虚拟节点
通常地在解决链表相关问题的时候习惯性地在给定的链表头加一个节点由于与题目无关是我们虚构用来方便计算处理边界条件的则把它称之为“虚拟节点”。⚠️注意后面涉及链表相关的问题会常用到虚拟节点。
为了便于理解现在以链表 1 - 2 -3 为例画图说明 这里我们将原来 链表 1- 2- 3 加上了一个虚拟节点变成了 链表 -1 - 1 - 2 - 3
至于为什么要加这个虚拟节点下文在遍历链表的时候大有用处我们会详细的说现在只需要知道虚拟节点这个概念即可。
判断是否存在长度为K的子链表
回到实际问题仍以链表 1 - 2 -3 为例下图所示每一个节点都有两个属性
val 当前节点值next 下个节点 上图标注的整个链表下文统一用head表示head是从题目中函数入参拿到的哦
public ListNode reverseKGroup(ListNode head, int k)首先我们在链表头部加上一个虚拟节点并声明两个指针 prev 和 last 用来限定K长度子链表的边界。 因为我们在入参的head上加了头部的虚拟节点又加了两个指针因此我们重新定义个新的dummy链表。
新的dummy链表 -1 - 1 - 2 -3 并附加了两个指针 last 和 prev。
//模拟代码
//声明新的dummy链表比之前的head链表多加了一个虚拟节点值为-1指向head
ListNode dummy new ListNode(-1, head);
//在dummy链表上声明last指针注意这里没有开辟新的空间
ListNode prev dummy;
//注意以上两行代码可以简写与操作8大基本类型数据的声明是一样的道理刚接触链表的同学可能看着有点懵需要细心体会
ListNode dummy new ListNode(-1, head), prev dummy;
//在dummy链表上声明prev指针注意这里没有开辟新的空间
ListNode last prev;现在通过移动last指针移动的长度就是K所以会有这样的写法
//模拟代码
forint i 0i k;i{//循环K次每次移动last指针到下一个节点因为是从虚拟节点开始移动所以第一次移动后last一定指向dummy的第一个节点。last last.next;//移动完要判断下一个节点是否为null如果为null说明K循环未结束而当前节点是末尾节点了说明不足K个节点。直接返回dummy.next即可。if (last null) {return dummy.next;}
}通过K次循环last指针判断dummy链表是否存在合理值K直至last 为null
翻转长度为K的子链表
接着上面的实例我们假设K2那么dummy链表的第一次K循环结束应该是这样的
也就是说我们找到了符合K长度的子链表接下来需要开始对子链表进行翻转了。
增加虚拟节点的好处 还记得前面我们买了一个伏笔吧那就是为什么要在head原始链表头上加一个虚拟节点。看到这里我想你应该明白了那就是
翻转后的K长子链表需要与旧链表进行缝合那么就需要知道旧链表的被切割处的节点位置如果正好是前K个链表那么翻转后只有尾部需要缝合前面是没有节点的难道要在翻转前单独判断无头有尾的特殊情况吗而在head前面加了虚拟节点则正好解决了这个问题无论K子链表在dummy哪里一定都是与旧链表相连的、有头有尾的子链表。 如果不存在K长子链表则直接返回第1个节点就可以了因为后面的节点会跟着第一个节点这等于是对于入参head没有操作直接返回了。如果存在K长子链表翻转后那么从1到K已经进行了翻转无论后面又翻转了多少个K子节点返回的头节点就是K。所以两种情况又要单独判断了。但是加上虚拟节点无论是否翻转只需要返回dummy.next即可。
接下来我们看具体翻转K子链表的过程。思考为什么经过翻转后仍只需要返回dummy.next不翻转可以理解就是dummy.next
首先要考虑翻转的子链表的起始节点和末尾节点。末尾节点就是last起始节点应该是prev.next ,因为是动态变化的需要新加一个指针姑且称之为curr意为当前节点所以K长子链表长度应该从curr到last。
//这里curr的取值不能为 dummy.next因为prev和curr是随着多个K长子链表动态变化的而dummy则是一个固定的链表。
ListNode curr prev.next;确定了K长子链表现在对子链表进行翻转并将翻转后的片段拼接回dummy。 由于K长可变试想若是存在合理值K100那么翻转一次吗所以翻转的次数也是需要根据K长动态变化的。
// 比如当前假设情况K2 那么只需要循环一次即可。因为循环一次翻转了2个节点。同理多个节点道理如此。
for (int i 0; i k - 1; i) {}翻转实际上就是从K长度子链表的第一个节点curr与下一个节点next进行交换直至交换到last结束。由于curr会不断在循环后刷新所以next节点也是随curr节点动态变化的。 ListNode next curr.next;现在我们要做的事情是交换curr节点与next节点并保证交换后节点与dummy前后开口正确缝合。
首先切断curr与next的关联关系让curr直接跳过next指向next的下一个节点。
//原来curr与next相连现在这个操作相当于把curr的下个节点跳过了next节点给到了next下一个节点。
curr.next next.next;将prev节点K长子链表的头节点的下一个节点也指向next的下一个节点。
//切断原来next的下一个节点的关联关系因为上一步进行了1 - 3 关联, 3节点无需多一个重复被指向3节点必须是来自于curr的指向。所以把next节点重定向到prev后面。
next.next prev.next;将prev节点K长子链表的头节点重定向到next节点即可
prev.next next;将prevK长子链表的头节点指向下一轮要进行的K长翻转的头节点处
上面步骤实现了从curr到last的K长一次翻转动作由于K长子链表需要不断在dummy中遍历寻找是否存在多个K所以下一次循环K2的时候我们需要将K2的头节点指针重新定位。
//curr一定是K长子链表最末尾的一个节点所以将prev指针移动到curr节点。
prev curr;第二次K循环由于last指针需要移动两次但是节点3的next为空所以直接返回prev.next了。 代码梳理
完整代码实现 public static ListNode reverseKGroup(ListNode head, int k) {ListNode dummy new ListNode(-1, head), 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, next;for (int i 0; i k - 1; i) {next curr.next;curr.next next.next;next.next prev.next;prev.next next;}prev curr;}}public static void main(String[] args) {ListNode list1 new ListNode(1,new ListNode(2,new ListNode(3)));ListNode listNode reverseKGroup(list1, 2);//链表遍历while (listNode ! null) {System.out.println(listNode.val);listNode listNode.next;}}断点步骤拆解
GitHub代码地址
