Algorithm
Problem Name: 61. Rotate List
Given the head of a linked list, rotate the list to the right by k places.
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (head == NULL || k == 0) return head;
struct ListNode **p = &head;
struct ListNode *new_head = NULL;
int len = 0;
while (*p) {
p = &((*p)->next);
len++;
}
k = k % len; /* important */
if (k == 0) return head;
*p = head; /* tail->next = head, make a circle */
p = &head;
while (len > k) {
p = &((*p)->next);
len--;
}
new_head = *p; /* new_head = new_tail->next */
*p = NULL; /* new_tail = NULL */
return new_head;
}
int main() {
struct ListNode *l1 = (struct ListNode *)calloc(5, sizeof(struct ListNode));
struct ListNode **p = &l1;
int i;
for (i = 1; i < = 5; i++) {
(*p)->val = i;
(*p)->next = *p + 1;
p = &(*p)->next;
}
*p = NULL;
printf("List: ");
struct ListNode *q = l1;
while (q != NULL) {
printf("%d->", q->val);
q = q->next;
}
printf("N\n");
int k = 2;
printf("Rotate right by %d.\n", k);
struct ListNode *ret = rotateRight(l1, k);
printf("Result: ");
q = ret;
while (q != NULL) {
printf("%d->", q->val);
q = q->next;
}
printf("N\n");
return 0;
}
Input
head = [1,2,3,4,5], k = 2
Output
[4,5,1,2,3]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head || !head->next) return head;
int len = 0;
ListNode* p = head;
while(p) p = p->next, len++;
k = k % len;
if(k == 0) return head;
ListNode* slow = head;
ListNode* fast = head;
while(k > 0) fast = fast->next, k--;
while(fast->next) fast = fast->next, slow = slow->next;
ListNode* res = slow->next;
slow->next = NULL;
fast->next = head;
return res;
}
};
Input
head = [0,1,2], k = 4
Output
[2,0,1]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) {
return head;
}
int n = 0;
ListNode curr = head;
while (curr != null) {
n++;
curr = curr.next;
}
k = k % n;
if (k == 0) {
return head;
}
k = n - k;
curr = head;
while (k-- > 1) {
curr = curr.next;
}
ListNode newHead = curr.next;
curr.next = null;
curr = newHead;
while (curr != null && curr.next != null) {
curr = curr.next;
}
curr.next = head;
return newHead;
}
}
Input
head = [0,1,2], k = 4
Output
[2,0,1]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const rotateRight = function(head, k) {
if (head === null || head.next === null) return head;
const dummy = new ListNode(0);
dummy.next = head;
let fast = dummy,slow = dummy;
let i;
for (i = 0; fast.next != null; i++)//Get the total length
fast = fast.next;
for (let j = i - k % i; j > 0; j--) //Get the i-n%i th node
slow = slow.next;
fast.next = dummy.next; //Do the rotation
dummy.next = slow.next;
slow.next = null;
return dummy.next;
};
Input
head = [0,1,2], k = 4
Output
[2,0,1]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def rotateRight(self, head, k):
arr, count = [head], 0
root = last = head
while last and last.next and count < k:
last, count = last.next, count+1
arr.append(last)
if k != count:
k = k % (count+1)
last = arr[k]
if k == 0 or not last:
return head
curr = root
while last.next:
last, curr = last.next, curr.next
last.next, curr.next, start = root, None, curr.next
return start
Input
head = [0,1,2], k = 4
Output
[2,0,1]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _061_RotateList
{
public ListNode RotateRight(ListNode head, int k)
{
if (k <= 0 || head == null) { return head; }
var ptr = new ListNode(-1);
ptr.next = head;
int lenght = 0;
while (ptr.next != null)
{
ptr = ptr.next;
lenght++;
}
ptr.next = head;
var rest = lenght - k % lenght;
for (int i = 0; i < rest; i++)
{
ptr = ptr.next;
}
head = ptr.next;
ptr.next = null;
return head;
}
}
}
Input
head = [1,2,3,4,5], k = 2
Output
[4,5,1,2,3]