Last updated on January 19th, 2025 at 02:43 am
Here, we see a Rotate List LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Linked List, Two-Pointers
Level of Question
Medium
Rotate List LeetCode Solution
Table of Contents
1. Problem Statement
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]
2. Coding Pattern Used in Solution
The coding pattern used in this problem is “In-place Reversal of a LinkedList”. This pattern is commonly used when we need to modify the structure of a linked list, such as reversing, rotating, or rearranging its nodes. The key idea is to manipulate the pointers of the linked list nodes directly without using extra space.
3. Code Implementation in Different Languages
3.1 Rotate List C++
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) {
return head;
}
auto iter = head;
auto len = 1;
while (iter->next != nullptr) {
iter = iter->next; ++len;
}
iter->next = head;
iter = head;
for (int i = 0; i < len - (k % len) - 1; ++i) {
iter = iter->next;
}
head = iter->next;
iter->next = nullptr;
return head;
}
};
3.2 Rotate List Java
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head==null||head.next==null) return head;
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=dummy,slow=dummy;
int i;
for (i=0;fast.next!=null;i++)
fast=fast.next;
for (int j=i-k%i;j>0;j--)
slow=slow.next;
fast.next=dummy.next;
dummy.next=slow.next;
slow.next=null;
return dummy.next;
}
}
3.3 Rotate List JavaScript
var rotateRight = function(head, k) {
if (!head || !head.next || !k) return head;
const list = [];
let len = 0;
// put linked list into array
for (let cur = head; cur; cur = cur.next) {
list[len++] = cur;
}
// calculate the break position
const newHead = len - (k % len);
if (newHead === len) return head;
// change pointer
list[len - 1].next = head;
list[newHead - 1].next = null;
return list[newHead];
};
3.4 Rotate List Python
class Solution(object):
def rotateRight(self, head, k):
n, pre, current = 0, None, head
while current:
pre, current = current, current.next
n += 1
if not n or not k % n:
return head
tail = head
for _ in xrange(n - k % n - 1):
tail = tail.next
next, tail.next, pre.next = tail.next, None, head
return next
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(1) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(1) |
- The problem is solved using the In-place Reversal of a LinkedList pattern.
- The time complexity is O(n) for all implementations, as the list is traversed twice.
- The space complexity is O(1) for C++, Java, and Python, but O(n) for JavaScript due to the use of an array to store nodes.