700023. Rotate a Linked List
Here is a detailed Markdown blog post for the problem "Rotate a Linked List" on GeeksforGeeks:
Rotate a Linked List
Slug: rotate-a-linked-list
Difficulty: Medium
Id: 700023
Topic Tags: Linked List, Data Structures
Company Tags: Accolite, Amazon, Microsoft, MakeMyTrip
Summary
Rotate a linked list by k steps is a common problem in computer science. Given the head of a singly linked list and an integer k, return the head of the rotated linked list.
Detailed Explanation
To solve this problem, we will first analyze the problem statement and understand what it means to rotate a linked list. Rotating a linked list by k steps essentially means that we are moving the last k nodes to the front of the list. For example, if the original list is 1 -> 2 -> 3 -> 4 -> 5 and we want to rotate it by 2 steps, the resulting list will be 4 -> 5 -> 1 -> 2 -> 3.
Here's a step-by-step breakdown of the solution:
- First, we need to find the new tail of the rotated list. This is the node that was previously at position k.
- Next, we need to update the next pointer of the new tail to point to the original head of the list. This effectively moves the last k nodes to the front of the list.
- Finally, we return the new head of the rotated list, which is the node that was previously at position k-1.
Here's a diagram illustrating the rotation:
Original List: 1 -> 2 -> 3 -> 4 -> 5
Rotation by 2: 4 -> 5 -> 1 -> 2 -> 3
The time complexity of this solution is O(n), where n is the length of the linked list, because we need to traverse the entire list once. The space complexity is O(1) because we only use a constant amount of space to store the new head and tail.
Optimized Solutions
Java
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) {
return head;
}
int len = 0;
ListNode curr = head;
while (curr != null) {
len++;
curr = curr.next;
}
k = k % len;
ListNode newTail = head;
for (int i = 0; i < len - k - 1; i++) {
newTail = newTail.next;
}
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}