LeetCode - Rotate List
Problem statement
Given the head of a linked list, rotate the list to the right by k places.
Problem statement taken from: https://leetcode.com/problems/rotate-list
Example 1:
Input: head = [1, 2, 3, 4, 5], k = 2
Output: [4, 5, 1, 2, 3]
Example 2:
Input: head = [0, 1, 2], k = 4
Output: [2, 0, 1]
Constraints:
- The number of nodes in the list is in the range [0, 500]
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
Explanation
The problem mentions rotating the list to the right. We first have to get the total number of nodes in the list. If k is greater than the list length, we first take the modulo of k by list length and then subtract the value of k from the list length. If k is smaller, we subtract the value of k from the list length.
Note: If the problem mentioned left rotation, we won't subtract k by the length of the list.
Let's check the algorithm first:
// 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
C++ solution
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;
}
};
Golang solution
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 solution
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;
};
Dry Run
Let's dry-run our algorithm to see how the solution works.
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].