做玩网站怎么上传,昆明优化网站公司,重庆建设部网站,设计说明英语翻译目录
一、前言
二、题目描述
三、解题方法
⭐解题思路---闭合为环
#x1f34d; 案例图解
四、总结与提炼
五、共勉 一、前言 旋转链表 这道题#xff0c;可以说是--链表专题--#xff0c;最经典的一道题#xff0c;也是在面试中频率最高的一道题目#x…目录
一、前言
二、题目描述
三、解题方法
⭐解题思路---闭合为环 案例图解
四、总结与提炼
五、共勉 一、前言 旋转链表 这道题可以说是--链表专题--最经典的一道题也是在面试中频率最高的一道题目通常在面试中面试官可能会从多个方面考察这道题目所以大家需要对这道题目非常熟悉哦 本片博客就来详细的讲讲解一下 旋转链表 的实现方法让我们的面试变的更加顺利 二、题目描述 题目链接61. 旋转链表 - 力扣LeetCode 给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。 三、解题方法
⭐解题思路---闭合为环 根据题意我们可以假设链表是1−2−3−4−5移动位是 k我们分析如下 k5 的情况实际移动的位数就是 k 本身。k5 的情况
k 是 5 的整数倍链表不会发生位置变化。k 不是 5 的整数倍实际移动位数是 k%5 的值。 知道了上述的分析我们很容易就能理清思路流程如下 计算链表的长度链表最后一位值的 next 指向原链表首位数字形成闭环如下所示
// 环图
1 - 2 - 3 - 4 - 5
↑ ↓
↑ ↓← ← ← ← ← ← // 线性图
1 - 2 - 3 - 4 - 5 - 1 - 2 - 3 - 4 - 5 - 1 - 2 - 3 - 4 - 5 - .... 案例图解
开始计算链表的长度遍历整个链表 让整个链表形成闭环 旋转 k 2, cur 指针移动 n-k 次 建立新的头节点 复杂度分析
时间复杂度O(n)最坏情况下我们需要遍历该链表两次。空间复杂度O(1)。我们只需要常数的空间存储若干变量。 代码 class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {// 当只有 head 节点 和 head-next 节点的时候 直接返回 head 即可if(headnullptr || head-nextnullptr){return head;}// 计算链表长度ListNode* cur head;int n 1;while(cur-next!nullptr){cur cur-next;n;}// Kn , 实际移动的位数就是 K 本身// Kn k是n的整数倍链表不变// K不是5的整数倍实际移动位数是 K%n的值k k % n;if(k0){return head;}// 闭合为环 链接头节点// cur 此时的位置在 结尾处cur-next head;// 找出移动后链表的 最后一个非空节点n n-k;while(n--){cur cur-next;}// 建立新的头节点ListNode* newhead cur-next;cur-next nullptr;return newhead;}
}; 四、总结与提炼 最后我们来总结一下本文所介绍的内容本文讲解来一道力扣中有关 旋转链表 的题目这道题目是校招笔试面试中有关链表章节非常高频的一道题目大家下去一定要自己再画画图分析一下把这段代码逻辑自己实现一遍才能更好地掌握 五、共勉 以下就是我对 旋转链表 的理解如果有不懂和发现问题的小伙伴请在评论区说出来哦同时我还会继续更新对 链表专题 的理解请持续关注我哦
