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.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 public ListNode rotateRight(ListNode head, int k) {
9 if (head == null || k == 0) return head;
10 ListNode curr = head;
11 int length = 1;
12 while (curr.next != null) {
13 curr = curr.next;
14 length++;
15 }
16 curr.next = head; // Make it circular
17 k = k % length;
18 for (int i = 0; i < length - k; i++) {
19 curr = curr.next;
20 }
21 head = curr.next;
22 curr.next = null;
23 return head;
24 }
25
26 public static void main(String[] args) {
27 ListNode head = new ListNode(1);
28 head.next = new ListNode(2);
29 head.next.next = new ListNode(3);
30 head.next.next.next = new ListNode(4);
31 head.next.next.next.next = new ListNode(5);
32
33 Solution sol = new Solution();
34 head = sol.rotateRight(head, 2);
35
36 while (head != null) {
37 System.out.print(head.val + " ");
38 head = head.next;
39 }
40 }
41}This Java solution repeats the same steps as the C implementation. Make the list circular by connecting the last node back to the head. Calculate k % length to find the effective number of moves. Finally, walk through the circular list to form the desired result, closing it correctly upon completion.
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.
1#include <iostream>
2using namespace std;
3
4struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (!head || k == 0) return head;
ListNode* fast = head, *slow = head;
int length = 1;
while (fast->next) {
fast = fast->next;
++length;
}
fast->next = head;
k %= length;
for (int i = 0; i < length - k; i++) {
slow = slow->next;
fast = fast->next;
}
head = slow->next;
fast->next = NULL;
return head;
}
};
// Example usage
int main() {
auto *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
Solution sol;
head = sol.rotateRight(head, 2);
while (head) {
cout << head->val << " ";
head = head->next;
}
return 0;
}This C++ solution starts by counting the length and linking the last node to the head to form a loop. It then uses two pointers: a fast pointer that traverses k nodes firstly and a slow pointer that starts from the head. Then moving both forward will find the new head when the fast pointer completes the loop.