【算法专题--链表】旋转链表 -- 高频面试题（图文详解，小白一看就懂！！）

目录

一、前言

二、题目描述  

三、解题方法 

⭐解题思路---闭合为环

🍍 案例图解  

四、总结与提炼 

五、共勉   

---

一、前言

        旋转链表 这道题，可以说是--链表专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
       本片博客就来详细的讲讲解一下 旋转链表 的实现方法，让我们的面试变的更加顺利！！！ 

二、题目描述  

题目链接：61. 旋转链表 - 力扣（LeetCode）

• 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 

三、解题方法 

⭐解题思路---闭合为环

 根据题意，我们可以假设链表是：1−>2−>3−>4−>5，移动位是 k，我们分析如下：

k<5 的情况：实际移动的位数，就是 k 本身。
k>5 的情况：

• k 是 5 的整数倍：链表不会发生位置变化。
• k 不是 5 的整数倍：实际移动位数是 k%5 的值。

知道了上述的分析，我们很容易就能理清思路，流程如下：

1. 计算链表的长度
2. 链表最后一位值的 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(head==nullptr || head->next==nullptr){return head;}// 计算链表长度ListNode* cur = head;int n =1;while(cur->next!=nullptr){cur =cur->next;n++;}// K<n , 实际移动的位数，就是 K 本身// K>n ，k是n的整数倍，链表不变//       K不是5的整数倍，实际移动位数是 K%n的值k = k % n;if(k==0){return head;}// 闭合为环 ，链接头节点// cur 此时的位置在 结尾处cur->next = head;// 找出移动后链表的 最后一个非空节点n = n-k;while(n--){cur = cur->next;}// 建立新的头节点ListNode* newhead = cur->next;cur->next = nullptr;return newhead;}
};

---

四、总结与提炼 

        最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关 旋转链表 的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握

五、共勉   

        以下就是我对 旋转链表 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！