61.旋转链表--字节跳动

你应该比你现在强得多

题目描述

给定单链表，要求返回向右移动K位后的新链表

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

思路分析

1. 计算链表的长度

2. 计算实际需要移动的步数

3. 找到新的头节点

4. 断开链表并重新连接

完整代码

/*** 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) 。