Rotate List Problem: Given the head
of a linked list, rotate the list to the right by k
places.
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Table of Contents
Rotate List Problem Solution
Problem Solution In Python
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if head == None: return
values = []
dummay = ListNode()
cur = dummay
while head:
values.append(head.val)
head = head.next
for i in range(k % len(values)):
values.insert(0,values.pop())
for j in values:
cur.next = ListNode(j)
cur = cur.next
return dummay.next
Problem Solution In Java
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null) return head;
ListNode p = head;
int count = 1;
while(p.next!= null){
count++;
p = p.next;
}
k = k % count;
p.next = head; /*make a circle here*/
p = head;
for(int i = 0; i < count - k - 1; i++){
p = p.next;
}
ListNode dummy = p.next;
p.next = null;
return dummy;
}
}
Problem Solution In C++
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL || head->next == NULL) return head;
int nodes = 1;
ListNode *temp = head;
while(temp->next != NULL){
temp = temp->next;
nodes++;
}
k = k % nodes;
if(k == 0)return head;
int i = 0;
ListNode *cur = head;
while(i<nodes-k-1){
cur = cur->next;
i++;
}
ListNode *newHead = cur->next;
temp->next = head;
cur->next = NULL;
return newHead;
}
};
Problem Solution In C
struct ListNode* rotateRight(struct ListNode* head, int k){
int length = 0;
struct ListNode* tmp;
struct ListNode* tmp2;
tmp = head;
while (tmp) {
length++;
tmp2 = tmp;
tmp = tmp->next;
}
if (length == 0) {
return head;
}
k = k % length;
tmp = head;
for (int i = 0; i < length - k - 1; i++) {
tmp = tmp->next;
}
tmp2->next = head;
head = tmp->next;
tmp->next = NULL;
return head;
}