© Parineeth M R

** 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++

/* head: first node of the linked list 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) return head; /*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) return head; /*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*/ last->next = head; prev->next = NULL; /*pivot will be the new head*/ return pivot; }

## Java

/* head: first node of the linked list 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 */ public static LinkedListNode rotateList(LinkedListNode head, int k, int length) { LinkedListNode[] prevArray = new LinkedListNode[1]; /*If there are 0 or 1 nodes in the linked list, then simply return*/ if (length < 2) return head; /*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) return head; /*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*/ LinkedListNode pivot = findKthNodeFromEnd(head, k, length, prevArray); LinkedListNode prev = prevArray[0]; /*Find the last node in the linked list*/ LinkedListNode last = pivot; while (last.next != null) last = last.next; /*Make the last node point to head and the node previous to pivot point to null*/ last.next = head; prev.next = null; /*pivot will be the new head*/ return pivot; }

## Python

#head: first node of the linked list #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 def rotate(head, k, length): #If there are 0 or 1 nodes in the linked list, then simply return if (length < 2): return head #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): return head #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 pivot, prev = LinkedListNode.find_kth_node_from_end(head, k, length) #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 last.next = head prev.next = None #pivot will be the new head return pivot