Rotate List
Problem Description
Question
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
1
2
3
4
5
null
Output: [4,5,1,2,3]
4
5
1
2
3
null
Example 2:
Input: head = [0,1,2], k = 4
0
1
2
null
Output: [2,0,1]
2
0
1
null
Constraints:
- The number of nodes in the list is in the range
[0, 500]. - -100 <= Node.val <= 100
- 0 <= k <= 2 * 109
Solve it on LeetCode
Approaches
1. Convert to Array
Intuition:
The basic idea in this approach is to first convert the linked list to an array. Once we have the array representation, rotating the list becomes straightforward. After performing the rotation on the array, we convert it back to a linked list.
Steps:
- Convert the linked list to an array.
- Rotate the array k times to the right.
- Convert the array back to a linked list.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the list. Conversion to and from the array takes linear time.
- Space Complexity: O(N), for storing the nodes in an ArrayList.
2. Iterative In-Place Rotation
Intuition:
Without converting to an array, we can perform the rotations directly on the linked list. This involves finding the new head and tail of the list after rotation.
Steps:
- Count the length of the list.
- Adjust k to handle cases where k is greater than the length.
- Make the list circular by connecting the tail to the head.
- Find the new tail and break the circle to form the new list.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the list.
- Space Complexity: O(1), no extra space except for pointers.