Rotate a Linked List
An algorithmic exercise that rotates the linked list by n, given the head node of a single linked list and the integer n.
Below are two examples. The linked list passed as an argument and the output after the integer n = 2 rotations.
Note that the value of n can be larger than the length of the linked list.
When n = -2,
Solution Runtime Complexity O(n) n is the length of the linked list. Memory Complexity O(1) No need to use new data structures. Pointer only.
Since "a picture is worth a thousand words", let's rotate the above linked list with n = 2 using the above algorithm.
RotateList.java
class RotateList{
private int getListSize(LinkedListNode head) {
LinkedListNode curr = head;
int listSize = 0;
while (curr != null) {
listSize++;
curr = curr.next;
}
return listSize;
}
private int adjustRotatationsNeeded(int n, int length) {
return n < 0 ? length - (n * -1) % length : n % length;
}
public LinkedListNode rotate_list(LinkedListNode head, int n) {
int listSize = 0;
listSize = getListSize(head);
n = adjustRotatationsNeeded(n, listSize);
if (n == 0) {
return head;
}
// Find the startNode of rotated list.
// If we have 1,2,3,4,5 where n = 2,
// 4 is the start of rotated list
LinkedListNode temp = head;
int rotationsCount = listSize - n - 1;
while(rotationsCount > 0) {
temp = temp.next;
rotationsCount--;
}
LinkedListNode new_head = temp.next;
temp.next = null;
LinkedListNode tail = new_head;
while (tail.next != null) {
tail = tail.next;
}
tail.next = head;
head = new_head;
return new_head;
}
}
Recommended Posts