【算法--链表】61.旋转链表--通俗讲解

一、题目是啥？一句话说清

给你一个链表，将链表每个节点向右移动 k 个位置，相当于把链表的最后 k 个节点移动到链表的前面。

示例：

• 输入：head = [1,2,3,4,5], k = 2
• 输出：[4,5,1,2,3]（最后2个节点4和5移动到了前面）

二、解题核心

先计算链表长度，然后找到新链表的头节点和尾节点，重新连接链表。 这就像把一列火车的最后几节车厢连接到火车的前面。

三、关键在哪里？（3个核心点）

想理解并解决这道题，必须抓住以下三个关键点：

1. 处理 k 大于链表长度的情况

• 是什么：如果 k 大于链表长度，实际有效的旋转次数是 k 对链表长度取模后的值。
• 为什么重要：因为旋转链表长度倍数次相当于没有旋转，取模可以避免不必要的操作。

2. 找到新链表的头节点和尾节点

• 是什么：新头节点是原链表的倒数第 k 个节点，新尾节点是原链表的倒数第 k+1 个节点。
• 为什么重要：只有正确找到这些节点，才能正确断开和重新连接链表。

3. 重新连接链表

• 是什么：将原链表的尾节点连接到头节点，并将新尾节点的 next 置为 null。
• 为什么重要：这是形成新链表的关键步骤，如果连接错误会导致链表断开或形成环。

四、看图理解流程（通俗理解版本）

让我们用链表 1 → 2 → 3 → 4 → 5 和 k=2 的例子来可视化过程：

1. 计算链表长度：

   • 链表有 5 个节点，所以长度 n = 5。
   • 计算有效 k = 2 % 5 = 2（因为旋转 5 次相当于不旋转）。

2. 找到关键节点：

   • 新头节点应该是倒数第 2 个节点，即节点 4。
   • 新尾节点应该是倒数第 3 个节点（即第 n - k = 3 个节点），即节点 3。
   • 原尾节点是节点 5。

3. 重新连接：

   • 将新尾节点（节点 3）的 next 置为 null。
   • 将原尾节点（节点 5）的 next 指向原头节点（节点 1）。
   • 新链表变为：4 → 5 → 1 → 2 → 3

4. 返回结果：返回新头节点 4。

五、C++ 代码实现（附详细注释）

#include <iostream>
using namespace std;// 链表节点定义
struct ListNode {int val;ListNode *next;ListNode() : val(0