Description:
Given the head of a linked list, rotate the list to the right by k places.
Examples:
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 in Python:
To solve the problem of rotating a linked list to the right by k places, we need to follow these steps:
Determine the length of the list: This is required to handle cases where k is larger than the length of the list.
Make the list circular: Connect the last node to the first node to create a circular list.
Find the new head position: Calculate the new head position by using the length of the list and the value of k.
Break the circular list: Set the next node of the new tail to None.
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# Base case: if the list is empty or has only one node, or k is 0, no rotation is needed
if not head or not head.next or k == 0:
return head
# Step 1: Determine the length of the list
length = 1
current = head
while current.next:
current = current.next
length += 1
# Step 2: Make the list circular
current.next = head
# Step 3: Find the new head position
# New head is at position length - (k % length) from the start
# k might be larger than length, hence use k % length
k = k % length
steps_to_new_head = length - k
# Step 4: Break the circular list at the new tail
new_tail = head
for _ in range(steps_to_new_head - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_headDetailed Explanation:
- Determine the length of the list:
- Traverse the list to count the number of nodes.
- Use a variable
lengthto store the count.
- Make the list circular:
- Connect the last node’s
nextpointer to the head, thus forming a circular linked list.
- Connect the last node’s
- Find the new head position:
- Calculate the effective rotations needed as
k % lengthto handle cases where k is larger than the length of the list. - Determine the position of the new head, which will be
length - (k % length)nodes from the current head.
- Calculate the effective rotations needed as
- Break the circular list:
- Traverse to the node just before the new head (new tail).
- Set the
nextpointer of the new tail toNone, effectively breaking the circular connection and forming the rotated list.
By following these steps, we efficiently rotate the linked list to the right by k places. This solution handles edge cases like empty lists, single-node lists, and large values of k gracefully.
Solution in Javascript:
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
// Base case: if the list is empty, has only one node, or no rotation is needed
if (!head || !head.next || k === 0) {
return head;
}
// Step 1: Determine the length of the list
let length = 1;
let current = head;
while (current.next) {
current = current.next;
length += 1;
}
// Step 2: Make the list circular
current.next = head;
// Step 3: Find the new head position
// k might be larger than length, hence use k % length
k = k % length;
let stepsToNewHead = length - k;
// Step 4: Break the circular list at the new tail
let newTail = head;
for (let i = 1; i < stepsToNewHead; i++) {
newTail = newTail.next;
}
let newHead = newTail.next;
newTail.next = null;
return newHead;
};Solution in Java:
Java
/**
* 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) {
// Base case: if the list is empty, has only one node, or no rotation is needed
if (head == null || head.next == null || k == 0) {
return head;
}
// Step 1: Determine the length of the list
ListNode current = head;
int length = 1;
while (current.next != null) {
current = current.next;
length += 1;
}
// Step 2: Make the list circular
current.next = head;
// Step 3: Find the new head position
// k might be larger than length, hence use k % length
k = k % length;
int stepsToNewHead = length - k;
// Step 4: Break the circular list at the new tail
ListNode newTail = head;
for (int i = 1; i < stepsToNewHead; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode RotateRight(ListNode head, int k) {
// Base case: if the list is empty, has only one node, or no rotation is needed
if (head == null || head.next == null || k == 0) {
return head;
}
// Step 1: Determine the length of the list
ListNode current = head;
int length = 1;
while (current.next != null) {
current = current.next;
length += 1;
}
// Step 2: Make the list circular
current.next = head;
// Step 3: Find the new head position
// k might be larger than length, hence use k % length
k = k % length;
int stepsToNewHead = length - k;
// Step 4: Break the circular list at the new tail
ListNode newTail = head;
for (int i = 1; i < stepsToNewHead; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}