[61] 旋转链表
https://leetcode-cn.com/problems/rotate-list/description/
- algorithms
- Medium (40.61%)
- Likes: 496
- Dislikes: -
- Total Accepted: 139.3K
- Total Submissions: 337K
- Testcase Example: ‘[1,2,3,4,5]\n2’
- Source Code: 61.rotate-list.cpp
给你一个链表的头节点 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
方法1: 快慢指针, 首尾相连
思路: 旋转链表, 使节点移动, 可以将原链表转化为循环链表, 找到符合题意的头节点的位置即可
步骤:
- 设置两指针
fast
和slow
,fast
指针用于探索链表尾部, 构建循环链表,slow
指针用于确定头节点的位置 - 遍历链表, 记录链表长度(
count
), 找到链表尾部, 将尾部指向head
, 构建循环链表 - 移动
slow
指针, 题目要求将节点向右移动k
个位置, 等价于将头指针向左移动count - k
个位置, 为了避免k > count
时多余的移动, 所以应向左移动count - k % count
个位置
小Tips
遇到链表不要吝啬变量的使用, 比如本题, 使用双指针比使用单指针要快上不少
单指针
双指针
链表旋转, 移动
k
个位置, 向左移动等价于 头指针向右移动k % count
个位置 , 向右移动等价于 头指针向右移动count - k % count
个位置.count
为链表长度
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head || k == 0) return head;
ListNode* fast = head;
ListNode* slow = head;
int count = 1;
while(fast->next){
fast = fast->next;
++count;
}
fast->next = head;
k = count - k % count;
while(k-- > 1) slow = slow->next;
head = slow->next;
slow->next = nullptr;
return head;
}
};
复杂度分析:
- 时间复杂度:
O(n)
, 最多需要两次遍历 - 空间复杂度:
O(1)