做视频搬运工的网站外贸网站空间
你应该比你现在强得多
题目描述
给定单链表，要求返回向右移动K位后的新链表
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
思路分析
-
计算链表的长度
-
计算实际需要移动的步数
-
找到新的头节点
-
断开链表并重新连接
完整代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {// 边界条件检查：如果链表为空、只有一个节点或 k 为 0，直接返回原链表if (head==NULL || head->next==NULL || k == 0) {return head;}// 1. 计算链表的长度int n = 1; // 链表长度初始化为 1，因为从第一个节点开始ListNode* tail = head; // tail 指针用于找到链表的末尾节点while (tail->next) { // 遍历链表直到最后一个节点tail = tail->next; // 移动到下一个节点n++; // 计数器增加}// 2. 计算实际需要移动的步数k = k % n; // k 对链表长度取模，避免不必要的重复旋转if (k == 0) {return head; // 如果 k 为 0，说明不需要旋转，直接返回原链表}// 3. 找到新的头节点ListNode* newTail = head; // newTail 指针用于找到旋转后新的尾节点for (int i = 0; i < n - k - 1; i++) { // 移动到新尾节点的位置（n - k - 1）newTail = newTail->next; // 移动到下一个节点}ListNode* newHead = newTail->next; // 新头节点是新尾节点的下一个节点// 4. 断开链表并重新连接newTail->next = nullptr; // 断开新尾节点与新头节点的连接tail->next = head; // 将原链表的尾节点连接到原链表的头节点，形成环return newHead; // 返回旋转后的新头节点}
};分析逻辑
1. 边界条件检查
-
如果链表为空（
head==NULL），或者链表只有一个节点（head->next==NULL），或者k为 0，直接返回原链表。 -
这些情况下链表不需要进行任何旋转操作。
2. 计算链表长度
-
使用
tail指针从链表头开始遍历，直到链表的末尾（tail->next为nullptr）。 -
在遍历过程中，计数器
n记录链表的长度。
3. 计算实际移动步数
-
由于旋转
k次相当于旋转k % n次，因为旋转n次后链表会回到原来的状态。 -
如果
k % n == 0，说明不需要旋转，直接返回原链表。
4. 找到新的头节点
-
使用
newTail指针从链表头开始，移动n - k - 1步，到达旋转后的新尾节点。 -
newTail->next就是旋转后的新头节点。
5. 断开链表并重新连接
-
将新尾节点 (
newTail) 的next指针设为nullptr，断开与新头节点的连接。 -
将原链表的尾节点 (
tail) 的next指针指向原链表的头节点 (head)，形成一个新的链表环。 -
返回新的头节点
newHead，完成链表的旋转操作。
总结
-
该算法通过计算链表长度和实际旋转步数，找到新的头节点和尾节点，并重新连接链表，实现链表的右旋转。
-
时间复杂度为 O(n)，空间复杂度为O(1) 。