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

一、前言

二、题目描述

三、解题方法

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

🍍 案例图解

四、总结与提炼

五、共勉

一、前言

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

二、题目描述

题目链接：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;
    }
};