Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
Given the head of a linked list, rotate the list to the right by k places.
Input/Output Specifications
- Input: Head of a linked list and integer k
- Output: Head of the rotated linked list
- Constraints:
- The number of nodes in the list is in the range [0, 500]
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10^9
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]
Solutions
Approach 1: Connect Tail to Head and Break at Position
This approach connects the tail to head to form a circle, then breaks the circle at the correct position.
Algorithm:
- Handle edge cases (empty list, single node, k = 0)
- Find the tail and count total nodes
- Calculate effective rotation: k % length
- Connect tail to head to form a circle
- Find the new tail (length - k positions from head)
- Break the circle at the new tail
- Return the new head
Python:
def rotateRight(head, k):
"""
Rotate linked list to the right by k places
Time: O(n)
Space: O(1)
"""
if not head or not head.next or k == 0:
return head
# Find tail and count nodes
tail = head
length = 1
while tail.next:
tail = tail.next
length += 1
# Calculate effective rotation
k = k % length
if k == 0:
return head
# Connect tail to head to form circle
tail.next = head
# Find new tail (length - k positions from head)
new_tail = head
for _ in range(length - k - 1):
new_tail = new_tail.next
# Break circle and return new head
new_head = new_tail.next
new_tail.next = None
return new_head
Java:
class Solution {
/**
* Rotate linked list to the right by k places
* Time: O(n)
* Space: O(1)
*/
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Find tail and count nodes
ListNode tail = head;
int length = 1;
while (tail.next != null) {
tail = tail.next;
length++;
}
// Calculate effective rotation
k = k % length;
if (k == 0) {
return head;
}
// Connect tail to head to form circle
tail.next = head;
// Find new tail (length - k positions from head)
ListNode newTail = head;
for (int i = 0; i < length - k - 1; i++) {
newTail = newTail.next;
}
// Break circle and return new head
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
Go:
// rotateRight - Rotate linked list to the right by k places
// Time: O(n)
// Space: O(1)
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// Find tail and count nodes
tail := head
length := 1
for tail.Next != nil {
tail = tail.Next
length++
}
// Calculate effective rotation
k = k % length
if k == 0 {
return head
}
// Connect tail to head to form circle
tail.Next = head
// Find new tail (length - k positions from head)
newTail := head
for i := 0; i < length-k-1; i++ {
newTail = newTail.Next
}
// Break circle and return new head
newHead := newTail.Next
newTail.Next = nil
return newHead
}
JavaScript:
/**
* Rotate linked list to the right by k places
* Time: O(n)
* Space: O(1)
*/
function rotateRight(head, k) {
if (head === null || head.next === null || k === 0) {
return head;
}
// Find tail and count nodes
let tail = head;
let length = 1;
while (tail.next !== null) {
tail = tail.next;
length++;
}
// Calculate effective rotation
k = k % length;
if (k === 0) {
return head;
}
// Connect tail to head to form circle
tail.next = head;
// Find new tail (length - k positions from head)
let newTail = head;
for (let i = 0; i < length - k - 1; i++) {
newTail = newTail.next;
}
// Break circle and return new head
const newHead = newTail.next;
newTail.next = null;
return newHead;
}
C#:
public class Solution {
/// <summary>
/// Rotate linked list to the right by k places
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode RotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Find tail and count nodes
ListNode tail = head;
int length = 1;
while (tail.next != null) {
tail = tail.next;
length++;
}
// Calculate effective rotation
k = k % length;
if (k == 0) {
return head;
}
// Connect tail to head to form circle
tail.next = head;
// Find new tail (length - k positions from head)
ListNode newTail = head;
for (int i = 0; i < length - k - 1; i++) {
newTail = newTail.next;
}
// Break circle and return new head
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}
Approach 2: Reverse and Rotate
This approach reverses the entire list, then reverses the first k elements and the remaining elements separately.
Algorithm:
- Handle edge cases
- Calculate effective rotation: k % length
- Reverse the entire list
- Reverse the first k elements
- Reverse the remaining elements
- Return the head
Python:
def rotateRightReverse(head, k):
"""
Rotate using reverse approach
Time: O(n)
Space: O(1)
"""
if not head or not head.next or k == 0:
return head
# Count nodes
length = 0
current = head
while current:
length += 1
current = current.next
# Calculate effective rotation
k = k % length
if k == 0:
return head
# Reverse entire list
head = reverseList(head)
# Reverse first k elements
current = head
for _ in range(k - 1):
current = current.next
# Reverse remaining elements
current.next = reverseList(current.next)
return head
def reverseList(head):
"""Helper function to reverse a linked list"""
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
Java:
class Solution {
/**
* Rotate using reverse approach
* Time: O(n)
* Space: O(1)
*/
public ListNode rotateRightReverse(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Count nodes
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// Calculate effective rotation
k = k % length;
if (k == 0) {
return head;
}
// Reverse entire list
head = reverseList(head);
// Reverse first k elements
current = head;
for (int i = 0; i < k - 1; i++) {
current = current.next;
}
// Reverse remaining elements
current.next = reverseList(current.next);
return head;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
}
Go:
// rotateRightReverse - Rotate using reverse approach
// Time: O(n)
// Space: O(1)
func rotateRightReverse(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
// Count nodes
length := 0
current := head
for current != nil {
length++
current = current.Next
}
// Calculate effective rotation
k = k % length
if k == 0 {
return head
}
// Reverse entire list
head = reverseList(head)
// Reverse first k elements
current = head
for i := 0; i < k-1; i++ {
current = current.Next
}
// Reverse remaining elements
current.Next = reverseList(current.Next)
return head
}
// reverseList - Helper function to reverse a linked list
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
current := head
for current != nil {
nextTemp := current.Next
current.Next = prev
prev = current
current = nextTemp
}
return prev
}
JavaScript:
/**
* Rotate using reverse approach
* Time: O(n)
* Space: O(1)
*/
function rotateRightReverse(head, k) {
if (head === null || head.next === null || k === 0) {
return head;
}
// Count nodes
let length = 0;
let current = head;
while (current !== null) {
length++;
current = current.next;
}
// Calculate effective rotation
k = k % length;
if (k === 0) {
return head;
}
// Reverse entire list
head = reverseList(head);
// Reverse first k elements
current = head;
for (let i = 0; i < k - 1; i++) {
current = current.next;
}
// Reverse remaining elements
current.next = reverseList(current.next);
return head;
}
/**
* Helper function to reverse a linked list
*/
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
C#:
public class Solution {
/// <summary>
/// Rotate using reverse approach
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode RotateRightReverse(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
// Count nodes
int length = 0;
ListNode current = head;
while (current != null) {
length++;
current = current.next;
}
// Calculate effective rotation
k = k % length;
if (k == 0) {
return head;
}
// Reverse entire list
head = ReverseList(head);
// Reverse first k elements
current = head;
for (int i = 0; i < k - 1; i++) {
current = current.next;
}
// Reverse remaining elements
current.next = ReverseList(current.next);
return head;
}
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next;
current.next = prev;
prev = current;
current = nextTemp;
}
return prev;
}
}
Key Insights
- Circular approach: Connect tail to head, then break at the right position
- Effective rotation: k % length eliminates unnecessary full rotations
- Two-pass solution: First pass to find tail and length, second pass to find new tail
- Edge case handling: Handle empty lists, single nodes, and k = 0
- Space optimization: Both approaches use O(1) extra space
Edge Cases
- Empty list
- Single node list
- k = 0 (no rotation needed)
- k >= length (multiple full rotations)
- k = length - 1 (rotate by 1)
Test Cases
# Test case 1: Normal rotation
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
# rotateRight(head1, 2) -> [4,5,1,2,3]
# Test case 2: k >= length
head2 = ListNode(0)
head2.next = ListNode(1)
head2.next.next = ListNode(2)
# rotateRight(head2, 4) -> [2,0,1]
# Test case 3: Single node
head3 = ListNode(1)
# rotateRight(head3, 1) -> [1]
# Test case 4: Empty list
head4 = None
# rotateRight(head4, 1) -> None
Follow-up Questions
- How would you rotate to the left instead of right?
- Can you solve this with O(1) space and O(1) time?
- How would you handle very large k values?
- What if the list has cycles?
Common Mistakes
- Not handling k >= length case
- Incorrect calculation of new tail position
- Not properly breaking the circular connection
- Forgetting to handle edge cases
- Off-by-one errors in position calculation
- Memory leaks when not properly managing pointers