Given the head of a linked list, rotate the list to the right by k places.
Test Cases
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]
Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k){
if (k==0 || head == NULL || head->next == NULL) return head;
struct ListNode* fast = head;
int n=0;
while(fast != NULL) {
fast = fast->next;
n++;
}
if (n <= k) k = k%n;
if (k==0) return head;
fast = head;
while(k>0) {
k--;
fast = fast->next;
}
struct ListNode* slow = head;
while (fast->next != NULL) {
slow = slow->next;
fast = fast->next;
}
fast->next = head;
struct ListNode* newhead = slow->next;
slow->next = NULL;
return newhead;
}/**
* 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 (k==0 || head == NULL || head->next == NULL) return head;
ListNode* fast = head;
int n=0;
while(fast != NULL) {
fast = fast->next;
n++;
}
if (n <= k) k = k%n;
if (k==0) return head;
fast = head;
while(k>0) {
k--;
fast = fast->next;
}
ListNode* slow = head;
while (fast->next != NULL) {
slow = slow->next;
fast = fast->next;
}
fast->next = head;
ListNode* newhead = slow->next;
slow->next = NULL;
return newhead;
}
};/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k==0 || head == null || head.next == null) return head;
ListNode fast = head;
int n=0;
while(fast != null) {
fast = fast.next;
n++;
}
if (n <= k) k = k%n;
if (k==0) return head;
fast = head;
while(k>0) {
k--;
fast = fast.next;
}
ListNode slow = head;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
fast.next = head;
ListNode newhead = slow.next;
slow.next = null;
return newhead;
}
}