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.
1function ListNode(val) {
2 this.val = val;
3 this.next = null;
4}
5
6var rotateRight = function(head, k) {
7 if (!head || k === 0) return head;
8 let length = 1;
9 let current = head;
10 while (current.next) {
11 current = current.next;
12 length++;
13 }
14 current.next = head; // make it circular
15 k %= length;
16 for (let i = 0; i < length - k; i++) {
17 current = current.next;
18 }
19 head = current.next;
20 current.next = null;
21
22 return head;
23};
24
25// Example usage
26let head = new ListNode(1);
27head.next = new ListNode(2);
28head.next.next = new ListNode(3);
29head.next.next.next = new ListNode(4);
30head.next.next.next.next = new ListNode(5);
31let newHead = rotateRight(head, 2);
32let current = newHead;
33while (current != null) {
34 console.log(current.val);
35 current = current.next;
36}This JavaScript solution follows the same approach. Consistently traverse to create a circular linked list, utilize k modulo length, and break the list at the appropriate point to achieve the desired rotation.
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.
1class ListNode:
2 def
This Python approach uses the length and circular linking technique alongside the two-pointer method. After calculating the mod value to deal with oversized k, a fast pointer forwards to skip k nodes while the slow pointer eventually lands on the desired new tail.