Rotate a linked list

© 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