力扣面试经典——61题

💡 参考代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 旋转链表，将链表每个节点向右移动k个位置
 * 
 * @param head 链表的头节点
 * @param k 移动的位置数
 * @return 返回旋转后的新链表头节点
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    // 边界条件处理：空链表或只有一个节点的情况
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 第一步：计算链表长度并形成环形链表
    struct ListNode* tail = head;
    int length = 1;  // 记录链表长度
    
    // 遍历到链表尾部，同时计算链表长度
    while (tail->next != NULL) {
        tail = tail->next;
        length++;
    }
    
    // 将链表连接成环
    tail->next = head;
    
    // 第二步：优化k值，避免不必要的完整旋转
    // 实际需要移动的位置是 k % length
    k = k % length;
    
    // 找到新的尾节点位置（从原头部移动 length-k 步）
    // 新的头节点就在新尾节点的下一个位置
    for (int i = 0; i < length - k; i++) {
        tail = tail->next;
    }
    
    // 第三步：在正确位置断开环，形成新的链表
    head = tail->next;  // 新的头节点
    tail->next = NULL;  // 断开环，形成线性链表
    
    return head;
}

📖 总结：

点击展开题目总结

🤔 旋转链表

---

1️⃣ 题目核心信息

🎯 功能描述：给定一个链表和一个整数k，将链表每个节点向右移动k个位置

📥 输入输出：

• 输入：
  • head: 链表的头节点
  • k: 向右移动的位数
• 输出：返回旋转后链表的头节点

---

2️⃣ 实现原理

💡 核心思路：将链表构成环形结构，通过找到新的断点来实现旋转效果

📋 实现步骤：

1. 特殊情况判断：空链表或单节点直接返回
2. 遍历链表计算长度，并将链表尾部连接到头部构成环
3. 计算实际需要移动的位置：k % length
4. 找到新的尾节点位置并断开环，形成新的链表

---

3️⃣ 关键点解析

通过将链表连接成环的方式，避免了逐个移动节点的低效操作，只需要找到正确的断开点即可完成旋转。

🎯 代码技巧

• 使用环形链表思想简化旋转操作
• 通过取模运算优化大数值的k
• 利用一次遍历同时计算长度和找到尾节点

4️⃣ 使用场景

✅ 适用情况：

• 链表数据结构的旋转操作
• 缓冲区循环使用场景
• 数据轮转处理需求

⚠️ 前提条件：

• 链表节点数目在[0, 500]范围内
• k值在[0, 2*10^9]范围内

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，其中n是链表长度，需要遍历一次链表
• 💾 空间复杂度：O(1)，只使用常数额外空间

6️⃣ 注意事项

🚩 边界情况：

• 空链表或只有一个节点
• k值为0或链表长度的整数倍
• k值大于链表长度

💥 易错点：

• 忘记处理空链表情况
• 没有对k值进行取模优化
• 断开环时位置计算错误

7️⃣ 补充说明

以示例1为例：head = [1,2,3,4,5], k = 2

初始状态：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

第一步：计算链表长度并形成环

• 遍历链表得到长度 length = 5
• 将尾节点5连接到头节点1，形成环

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

第二步：优化k值

• k = k % length = 2 % 5 = 2
• 实际需要移动2个位置

第三步：找到新的断开点

• 需要移动2位，意味着新的头节点是原链表倒数第2个节点(4)
• 从当前尾节点(5)开始，向前移动 length - k = 5 - 2 = 3 步找到新的尾节点(3)
  • 第1步：5 -> 1
  • 第2步：1 -> 2
  • 第3步：2 -> 3
• 新的尾节点是3，新的头节点是3的下一个节点4

第四步：断开环并形成新链表

• 保存新头节点：head = 4
• 断开连接：3->next = NULL
• 最终结果：4 -> 5 -> 1 -> 2 -> 3 -> NULL

这样就完成了向右移动2位的旋转操作。

加载评论中...