自己的做法
算法思想
链表长度为n，如果k >=n的话， 则移动 k mod n 和移动k个位置效果是一样的。
新链表的头节点应该是原链表的第 n - (k mod n) 个节点(从0开始)。
所以可以先找到第 n - (k mod n)个节点的前一个节点 和 最后一个节点。
让新链表指针指向第 n - (k mod n)个节点。
然后修改它的前一个节点的next指针为空，最后一个节点的next指针为原链表头节点即可。
注意：k 为 0 时，或给定链表为空或只有一个节点时，直接返回即可。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == nullptr || head->next == nullptr) {return head;}
int size = 0;
ListNode * node = head;
while(node) {
size++;
node = node->next;
}
k = k % size;
if(k == 0) {
return head;
}
ListNode * former = head;
ListNode * latter = head;
for(int i = 0; i < k; i++) {
latter = latter->next;
}
while(latter->next) {
former = former->next;
latter = latter->next;
}
ListNode * newHead = former->next;
latter->next = head;
former->next = nullptr;
return newHead;
}
};
|
性能分析
时间复杂度：遍历了两遍链表，为O(n)。
空间复杂度：O(1)。
参考做法
算法思想
同样，先链表获得链表长度n。
那么第(n - k mod n) 个节点就是新链表的头节点。
将原链表闭合为环，即最后一个节点指向第一个节点。
然后从原链表头节点开始向后移动 (n - k mod n - 1)步，指向新链表头节点的前一个节点。
断开即可。
算法实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == nullptr || head->next == nullptr) {
return head;
}
ListNode * node = head;
int n = 1;
for(;node->next != nullptr; n++, node = node->next);
k = k % n;
if(k == 0) {return head;}
node->next = head;
node = head;
for(int i = 0; i < n - k - 1; i++) {
node = node->next;
}
ListNode * newHead = node->next;
node->next = nullptr;
return newHead;
}
};
|
性能分析
时间复杂度：O(n)。
空间复杂度：O(1)。