欢迎访问LeetCode题解合集
题目描述
给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
题解:
法一:
假设一个数组有 n
个元素,现在想将其元素循环右移 k
个位置,如何实现额外空间复杂度为 $O(1)$ 的算法。
具体做法就是:
-
将
1~n-k
逆序 -
将
n-k+1~n
逆序 -
将
1~n
逆序
这样就可以将数组中的每个元素循环右移 k
个单位了。
回到这题,我们采用同样的思路,将链表的前 n-k
个节点逆序,然后将后 k
个节点逆序,然后将整体逆序。
有一个小技巧:由于 k
可能很大,需要将它对 n
取模,n
为链表节点个数。
时间复杂度:$O(n)$
额外空间复杂度:$O(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) {
if ( !head || !head->next || !k ) return head;
int n = 0;
ListNode *p = head;
while ( p ) {
++n;
p = p->next;
}
k %= n;
if ( !k ) return head;
ListNode dummy;
ListNode* tail = &dummy;
tail->next = head;
ListNode *pre = head, *q = nullptr;
p = head->next;
for ( int i = 1; i < n - k; ++i ) {
q = p->next;
p->next = pre;
pre = p;
p = q;
}
tail->next = pre;
pre = p;
p = p->next;
pre->next = nullptr;
for ( int i = 1; i < k; ++i ) {
q = p->next;
p->next = pre;
pre = p;
p = q;
}
head->next = pre;
pre = tail->next;
p = pre->next;
pre->next = nullptr;
while ( p ) {
q = p->next;
p->next = pre;
pre = p;
p = q;
}
tail->next = pre;
return tail->next;
}
};
/*
时间:4ms,击败:98.96%
内存:11.3MB,击败:74.09%
*/
法二:
快慢指针。
方法一的实现太麻烦了,完全照搬 数组存储 的思路。而这题是 链表存储 ,链表的物理地址不连续,也就是说我们没必要像 数组 那样翻过来翻过去的。
假设我们找到了分界点,first
指向第 n
个节点, second
指向第 n - k
个节点,把两部分拼接起来就好了,详情见代码:
/**
* 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) {
if ( !head || !head->next || !k ) return head;
int n = 0;
ListNode *p = head;
while ( p ) {
++n;
p = p->next;
}
k %= n;
if ( !k ) return head;
ListNode* first = head;
while ( k-- && first ) first = first->next;
ListNode* second = head;
while ( first->next ) {
first = first->next;
second = second->next;
}
first->next = head;
head = second->next;
second->next = nullptr;
return head;
}
};
/*
时间:4ms,击败:98.96%
内存:11.4MB,击败:71.99%
*/
其实还有一个小技巧,在求链表节点个数时,可以保存链表最后一个节点,这样只走前面的 n-k
步找到分界点,不需要走剩下的 k
步。
具体见代码:
/**
* 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) {
if ( !head || !head->next || !k ) return head;
int n = 0;
ListNode *p = head, *tail = nullptr;
while ( p ) {
if ( !p->next ) tail = p;
++n;
p = p->next;
}
k %= n;
if ( !k ) return head;
k = n - k;
ListNode* first = head;
ListNode* second = first;
while ( k-- && first ) second = first, first = first->next;
tail->next = head;
head = first;
second->next = nullptr;
return head;
}
};
/*
时间:4ms,击败:98.96%
内存:11.4MB,击败:72.38%
*/
法三:
还是快慢指针。
前面两种方法都是在 单向链表 上操作,此题也可以将链表变成 环形单链表 ,找到分界点断开即可。
/**
* 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) {
if ( !head || !head->next || !k ) return head;
int n = 0;
ListNode *p = head, *tail = nullptr;
while ( p ) {
if ( !p->next ) tail = p;
++n;
p = p->next;
}
k %= n;
if ( !k ) return head;
tail->next = head;
k = n - k;
ListNode *fast = head, *slow = head;
while ( k-- ) {
slow = fast;
fast = fast->next;
}
slow->next = nullptr;
return fast;
}
};
/*
时间:4ms,击败:98.96%
内存:11.3MB,击败:75.16%
*/