Question 7. Rotate a linked list by k positions

Consider the linked list A->B->C->D->E. If we rotate the linked list by k = 2 positions, then the linked list will become D->E->A->B->C. To perform the rotation we do the following:

1. Locate the kth node from the end (let’s call this node the pivot). If k = 2, we have to locate the second last node which in this case is D.

2. Make the node previous to the pivot point to NULL. So in this case C will point to NULL.

3. Traverse till the end of the linked list and make the last node point to the head of the linked list. So the last node E will point to the head A.

4. Make the pivot the head of the new linked list. So D will now become the new head.

Note that if k = length of linked list, then after rotation we end up with the original linked list. So we apply the formula, k = k % length to figure out the actual rotation required.

## C/C++

```
/*
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/
struct node* rotate_list(struct node *head, int k, int length)
{
struct node *pivot, *prev, *last;

/*If there are 0 or 1 nodes in the linked list, then simply return*/
if (length < 2)

/*If we shift by k times, then we get back the same linked list. So we
just have to shift k % length times*/
k = k % length;

/*If k is 0, then no need to shift*/
if (k == 0)

/*Find the kth node from the end. If k = 1, then pivot will have
the last node and prev will be the node previous to last node*/
prev = NULL;
pivot = find_kth_node_from_end(head, k, length, &prev);

/*Find the last node in the linked list*/
last = pivot;
while (last->next)
last = last->next;

/*Make the last node point to head and the node previous to pivot
point to NULL*/
prev->next = NULL;

/*pivot will be the new head*/
return pivot;
}

```

## Java

```
/*
k: by how many positions the linked list should be rotated
length: number of nodes in the linked list
Return value: first node of the rotated linked list
*/

/*If there are 0 or 1 nodes in the linked list, then simply return*/
if (length < 2)

/*If we shift by k times, then we get back the same linked list. So we
just have to shift k % length times*/
k = k % length;

/*If k is 0, then no need to shift*/
if (k == 0)

/*Find the kth node from the end. If k = 1, then pivot will have
the last node and prev will be the node previous to last node*/

/*Find the last node in the linked list*/
while (last.next != null)
last = last.next;

/*Make the last node point to head and the node previous to pivot
point to null*/
prev.next = null;

/*pivot will be the new head*/
return pivot;
}

```

## Python

```
#k: by how many positions the linked list should be rotated
#length: number of nodes in the linked list
#Return value: first node of the rotated linked list
@staticmethod
#If there are 0 or 1 nodes in the linked list, then simply return
if (length < 2):

#If we shift by k times, then we get back the same linked list.
#So we just have to shift k % length times
k = k % length

#If k is 0, then no need to shift
if (k == 0):

#Find the kth node from the end. If k = 1, then pivot will have
#the last node and prev will be the node previous to last node

#Find the last node in the linked list
last = pivot
while (last.next):
last = last.next

#Make the last node point to head and the node previous to pivot
#point to None