当前位置：首页 > news >正文

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

news 2025/6/23 3:25:29

一、前言

二、题目描述

三、解题方法

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

🍍 案例图解

四、总结与提炼

五、共勉

一、前言

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

二、题目描述

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

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

三、解题方法

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

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

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

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(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;}
};