Sponsored
Sponsored
This approach involves converting the linked list into a circular list and then breaking it at the correct point to achieve the required rotation.
By making the linked list a circular one, you can easily traverse k nodes from the end to set the new head and make necessary detachments.
Time Complexity: O(n) because we pass through the list twice, once to find the length and once to find the new head.
Space Complexity: O(1) since we only use a constant amount of extra space.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* rotateRight(struct ListNode* head, int k) {
10 if (!head || k == 0) return head;
11 struct ListNode *curr = head;
12 int length = 1;
13 while (curr->next) {
14 curr = curr->next;
15 length++;
16 }
17 curr->next = head; // Make it circular
18 k = k % length;
19 for (int i = 0; i < length - k; i++) {
20 curr = curr->next;
21 }
22 head = curr->next;
23 curr->next = NULL;
24 return head;
25}
26
27// Helper function to print the list
28void printList(struct ListNode *node) {
29 while (node != NULL) {
30 printf("%d ", node->val);
31 node = node->next;
32 }
33}
34
35// Example usage
36int main() {
37 struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
38 head->val = 1; head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
39 head->next->val = 2; head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
40 head->next->next->val = 3; head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
41 head->next->next->next->val = 4; head->next->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
42 head->next->next->next->next->val = 5; head->next->next->next->next->next = NULL;
43 head = rotateRight(head, 2);
44 printList(head);
45 return 0;
46}In this solution, we first determine the length of the list and then make it circular. We perform a modulus operation on k to handle cases where k is greater than the length, effectively making unnecessary additional full rotations. Finally, we iterate over the circular list to the correct point to form a valid, rotated list, detaching the circle.
In this approach, we utilize a two-pointer technique. We advance one pointer ahead by k nodes and then move another pointer from the start concurrently until the first pointer reaches the list's end. This way, the second pointer will eventually land on the node that will become the new tail.
Time Complexity: O(n) because it requires traversal for counting.
Space Complexity: O(1) as no extra space is used.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode RotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
ListNode fast = head, slow = head;
int length = 1;
while (fast.next != null) {
fast = fast.next;
length++;
}
fast.next = head; // form circular
k %= length;
for (int i = 0; i < length - k; i++) {
slow = slow.next;
fast = fast.next;
}
head = slow.next;
fast.next = null;
return head;
}
public static void Main() {
ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
Solution sol = new Solution();
ListNode newHead = sol.RotateRight(head, 2);
ListNode curr = newHead;
while (curr != null) {
Console.Write(curr.val + " ");
curr = curr.next;
}
}
}
In this C# solution, the logic is similar to the previous languages. After determining the length and connecting the end, the fast and slow pointers identify the correct division point. This method makes efficient use of mid-list pointer adjustments to achieve rotation.