Problem Statement:
Given the head of a linked list, rotate the list to the right by k places.
Examples:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
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 * 109
Approach:
- First, compute the length of the list.
- Adjust
kusing modulo:k = k % length. - Use two pointers: move one
ksteps ahead, then move both until the first reaches the end. - Rewire the pointers to rotate the list, breaking it at the new tail.
var rotateRight = function(head, k) {
if (!head || !head.next || k === 0) return head;
let length = 1;
let tail = head;
while (tail.next) {
tail = tail.next;
length++;
}
k = k % length;
if (k === 0) return head;
let stepsToNewHead = length - k;
let prev = null;
let curr = head;
while (stepsToNewHead--) {
prev = curr;
curr = curr.next;
}
prev.next = null;
tail.next = head;
return curr;
};
struct ListNode* rotateRight(struct ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
int length = 1;
struct ListNode* tail = head;
while (tail->next) {
tail = tail->next;
length++;
}
k = k % length;
if (k == 0) return head;
int steps = length - k;
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (steps--) {
prev = curr;
curr = curr->next;
}
prev->next = NULL;
tail->next = head;
return curr;
}
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
int length = 1;
ListNode* tail = head;
while (tail->next) {
tail = tail->next;
length++;
}
k = k % length;
if (k == 0) return head;
int steps = length - k;
ListNode* prev = nullptr;
ListNode* curr = head;
while (steps--) {
prev = curr;
curr = curr->next;
}
prev->next = nullptr;
tail->next = head;
return curr;
}
};
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
int length = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
length++;
}
k = k % length;
if (k == 0) return head;
int steps = length - k;
ListNode prev = null;
ListNode curr = head;
while (steps-- > 0) {
prev = curr;
curr = curr.next;
}
prev.next = null;
tail.next = head;
return curr;
}
}
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next or k == 0:
return head
length = 1
tail = head
while tail.next:
tail = tail.next
length += 1
k = k % length
if k == 0:
return head
steps = length - k
prev = None
curr = head
for _ in range(steps):
prev = curr
curr = curr.next
prev.next = None
tail.next = head
return curr
public class Solution {
public ListNode RotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) return head;
int length = 1;
ListNode tail = head;
while (tail.next != null) {
tail = tail.next;
length++;
}
k = k % length;
if (k == 0) return head;
int steps = length - k;
ListNode prev = null;
ListNode curr = head;
while (steps-- > 0) {
prev = curr;
curr = curr.next;
}
prev.next = null;
tail.next = head;
return curr;
}
}
