题目描述

给定一个链表，旋转链表，将链表中的每个节点向右移动 $k$ 个位置，其中 $k$ 是非负数。

示例 1:

输入: head = [1,2,3,4,5], k = 2
输出: [4,5,1,2,3]
解释:
向右旋转 1 步: [5,1,2,3,4]
向右旋转 2 步: [4,5,1,2,3]

示例 2:

输入: head = [0,1,2], k = 4
输出: [2,0,1]
解释:
向右旋转 1 步: [2,0,1]
向右旋转 2 步: [1,2,0]
向右旋转 3 步: [0,1,2]
向右旋转 4 步: [2,0,1]

约束:

• 链表中的节点数在范围 $[0,500]$ 内。
• $-100\le Node.val\le 100$。
• $0\le k\le 2\ast 10^9$。

---

解题思路

1. 特殊情况处理:

   • 如果链表为空或只有一个节点，或者 $k=0$，直接返回原链表。

2. 计算链表长度:

   • 遍历链表，计算链表长度$n$。

3. 优化旋转步数:

   • 由于旋转 $k$ 次相当于旋转 $k\%n$ 次，减少多余计算。

4. 找到旋转点:

   • 新的头节点的位置是 $n-(k\%n)$。需要找到链表中对应的位置，将链表断开并重新连接。

5. 形成环再断开:

   • 可以将链表连成环，然后在适当位置断开。

---

C 代码实现

以下是基于上述思路的 C 语言实现：

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct ListNode {int val;struct ListNode *next;
};// 旋转链表函数
struct ListNode* rotateRight(struct ListNode* head, int k) {if (!head || !head->next || k == 0) {return head; // 特殊情况直接返回}// 计算链表长度int n = 1;struct ListNode *tail = head;while (tail->next) {tail = tail->next;n++;}// 优化 k，计算实际旋转步数k = k % n;if (k == 0) {return head; // 如果 k 为 0，不需要旋转}// 将链表连成环tail->next = head;// 找到新头节点和新尾节点int stepsToNewHead = n - k;struct ListNode *newTail = head;for (int i = 1; i < stepsToNewHead; i++) {newTail = newTail->next;}struct ListNode *newHead = newTail->next;// 断开环newTail->next = NULL;return newHead;
}// 辅助函数：创建新节点
struct ListNode* createNode(int val) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));newNode->val = val;newNode->next = NULL;return newNode;
}// 辅助函数：打印链表
void printList(struct ListNode* head) {while (head) {printf("%d -> ", head->val);head = head->next;}printf("NULL\n");
}// 主函数测试
int main() {// 创建链表 [1, 2, 3, 4, 5]struct ListNode *head = createNode(1);head->next = createNode(2);head->next->next = createNode(3);head->next->next->next = createNode(4);head->next->next->next->next = createNode(5);printf("原始链表: ");printList(head);int k = 2;struct ListNode *rotated = rotateRight(head, k);printf("旋转链表后: ");printList(rotated);return 0;
}

---

代码解析

1. 特殊情况处理:

   • 如果链表为空、只有一个节点，或者 $k=0$，直接返回原链表，避免无意义操作。

2. 链表长度计算:

   • 遍历链表，记录长度 $n$ 并找到尾节点 tail。

3. 优化旋转步数:

   • 使用 $k\%n$ 计算有效旋转次数。如果结果为 0，说明无需旋转。

4. 形成环并找到新头:

   • 将链表尾节点连接到头节点，形成环。
   • 根据 stepsToNewHead 找到新尾节点 newTail，然后确定新头节点 newHead。

5. 断开环:

   • 将 newTail->next 设置为 NULL，完成旋转。

---

复杂度分析

• 时间复杂度: $O(n)$
  • 遍历链表计算长度需要 $O(n)$。
  • 找到新头节点需要 $O(n)$。
• 空间复杂度: $O(1)$
  • 只使用了常量级的额外空间。

---

测试结果

输入：

head = [1,2,3,4,5], k = 2

输出：

旋转链表后: 4 -> 5 -> 1 -> 2 -> 3 -> NULL