61. 旋转链表【力扣(LeetCode) 】

零、原题链接

61. 旋转链表

一、题目描述

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

二、测试用例

示例 1：

在这里插入图片描述

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

示例 2：

在这里插入图片描述

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

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

三、解题思路

3.1 三步走战略

基本思路：
先反转整个链表，再反转前 k 个结点，再反转后 n-k 个结点。【 k 是求余整个链表长度后的 k】
具体思路：
- 定义：函数 reverse ，用于反转链表（使用头插法实现）；
- 预处理：
  - 计算长度，提前返回不需要移动的情况；
  - 增加头指针，方便后续操作；
- 三步走：
  - 先反转整个链表；
  - 拆分链表，前 k 个为一个链表，后 n-k 个为一个链表；
  - 反转拆分后的两个链表；
  - 合并拆分后的两个链表；

3.2 闭合+断开

先计算链表长度，提前返回不需要移动的情况；
将链表闭合，形成一个环；
确定链表的最后一个结点和头结点，遍历到该结点并断开；

例如：

链表：abcde ，k = 2 ；
计算链表长度 n = 5 ；
链表闭环；
确定最后一个链表的位置 = n - (k%n) = 5 - (2%5)=3 ，所以第 3 个结点就是最后一个结点，那么第 4 个结点就是头结点；【往右移动两次，c 就是最后一个结点，d 就是头结点】

四、参考代码

4.1 三步走战略

时间复杂度： $\Omicron(n)$
空间复杂度： $\Omicron(1)$

/*** 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* reverse(ListNode* head) {ListNode* ans = new ListNode();ListNode *p = head, *t = nullptr;while (p != nullptr) {t = p->next;p->next = ans->next;ans->next = p;p = t;}return ans->next;}ListNode* rotateRight(ListNode* head, int k) {int n = 0;for (ListNode* p = head; p != nullptr; p = p->next)n++;if (n == 0 || k % n == 0)return head;ListNode* ans = new ListNode(0, head);ans->next = reverse(ans->next); // 全部反转ListNode* p = ans;for (k %= n; k > 0; k--)p = p->next;head = p->next;p->next = nullptr;p = ans->next;ans->next = reverse(ans->next); // 反转前 k 个p->next = reverse(head);        // 反转后 n-k 个并拼接链表return ans->next;}
};

4.2 闭合+断开

时间复杂度： $\Omicron(n)$
空间复杂度： $\Omicron(1)$

/*** 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) {int n = 0;ListNode* ans = new ListNode(0, head);ListNode* p = ans;while (p->next != nullptr) {p = p->next;n++;}if (n == 0 || k % n == 0) {return head;}p->next = ans->next;  // 闭合for (int i = n - (k % n); i > 0; i--) { // 确定最后一个结点位置p = p->next;}ans->next = p->next; // 确定头结点p->next = nullptr;	// 断开return ans->next;}
};