Постановка задачи
Учитывая голову связанного списка, поверните список вправо на k мест.
Постановка задачи взята с: https://leetcode.com/problems/rotate-list
Пример 1:
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Пример 2:
Input: head = [0, 1, 2], k = 4
Output: [2, 0, 1]
Ограничения:
- The number of nodes in the list is in the range [0, 500]
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
Объяснение
В проблеме упоминается поворот списка вправо. Сначала нам нужно получить общее количество узлов в списке. Если k больше длины списка, мы сначала берем модуль k по длине списка, а затем вычитаем значение k из длины списка. Если k меньше, мы вычитаем значение k из длины списка.
Примечание. Если проблема связана с поворотом влево, мы не будем вычитать k из длины списка.
Сначала проверим алгоритм:
// empty list
- if head == nil
- return head
- set ListNode *p = head
set listLength = 1
- loop while p->next != null
- update p = p->next
- increment listLength++
- if k > listLength
- k = k % listLength
- k = listLength - k
- if k == 0 || k == listLength
- return head
- set ListNode *current = head
- loop while k > 1 && current != null
- update current = current->next
- decrement k--
- if current == null
- return head
- update p->next = head
update head = current->next
update current->next = null
- return head
С++ решение
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head){
return head;
}
ListNode *p = head;
int listLength = 1;
while(p->next != NULL){
p = p->next;
listLength++;
}
if(k > listLength) {
k = k % listLength;
}
k = listLength - k;
if(k == 0 || k == listLength) {
return head;
}
ListNode *current = head;
while(k > 1 && current != NULL){
current = current->next;
k--;
}
if(current == NULL){
return head;
}
p->next = head;
head = current->next;
current->next = NULL;
return head;
}
};
Голанг решение
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
p := head
listLength := 1
for p.Next != nil {
p = p.Next
listLength++
}
if k > listLength {
k = k % listLength
}
k = listLength - k
if k == 0 || k == listLength {
return head
}
current := head
for k > 1 && current != nil {
current = current.Next
k--
}
if current == nil {
return head
}
p.Next = head
head = current.Next
current.Next = nil
return head
}
Javascript-решение
var rotateRight = function(head, k) {
if(!head) {
return head;
}
let p = head;
let listLength = 1;
while(p.next != null) {
p = p.next;
listLength++;
}
if(k > listLength) {
k = k % listLength;
}
k = listLength - k;
if(k == 0 || k == listLength){
return head;
}
let current = head;
while(k > 1 && current != null) {
current = current.next;
k--;
}
if(current == null){
return head;
}
p.next = head;
head = current.next;
current.next = null;
return head;
};
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
head
|
Input: [1, 2, 3, 4, 5], k = 2
Step 1: if !head
head == nil
false
Step 2: ListNode *p = head
int listLength = 1
Step 3: loop while p->next != nil
p = p->next
listLength++
The above loop reaches at the last node of the linked list.
listLength = 5
head p
| |
[1, 2, 3, 4, 5]
Step 4: if k > listLength
2 > 5
false
Step 5: k = listLength - k
= 5 - 2
= 3
Step 6: if k == 0 || k == listLength
3 == 0 || 3 == 5
false
Step 7: ListNode *current = head
head p
| |
current - [1, 2, 3, 4, 5]
Step 8: loop while k > 1 && current != NULL
3 > 1 && current != NULL
true
current = current->next
head p
| |
[1, 2, 3, 4, 5]
|
current
k--
k = 2
2 > 1 && current != NULL
true
current = current->next
head p
| |
[1, 2, 3, 4, 5]
|
current
k--
k = 1
1 > 1 && current != NULL
false
Step 9: if current == NULL
false
Step 10: p->next = head
head
|
p - [5, 1, 2, 3, 4]
|
current
head = current->next
head
|
p - [5, 1, 2, 3, 4]
|
current
current->next = NULL
head current
| |
[4, 5, 1, 2, 3]
Step 11: return head
So we return the answer as [4, 5, 1, 2, 3].
Первоначально опубликовано на https://alkeshghorpade.me.