Skip to main content

Rotate linked list clockwise by k nodes in c

Rotating linked list node clockwise

C program for Rotate linked list clockwise by k nodes. Here mentioned other language solution.

// Include header file
#include <stdio.h>
#include <stdlib.h>

/*
  C program for 
  Rotate a list by moving each element 
  k times to the right.
  Or clockwise rotation of linked list 
*/
// Linked list node
typedef struct LinkNode
{
	// Define useful field of LinkNode
	int data;
	struct LinkNode * next;
}LinkNode;

LinkNode * getLinkNode(int data)
{
	// Create dynamic memory of LinkNode
	LinkNode * ref = (LinkNode * ) malloc(sizeof(LinkNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->data = data;
	ref->next = NULL;
	return ref;
}
typedef struct SingleLL
{
	// Define useful field of SingleLL
	struct LinkNode * head;
	struct LinkNode * tail;
}SingleLL;

SingleLL * getSingleLL()
{
	// Create dynamic memory of SingleLL
	SingleLL * ref = (SingleLL * ) malloc(sizeof(SingleLL));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	ref->head = NULL;
	ref->tail = NULL;
	return ref;
}
// Add new Node at end of linked list 
void addNode(SingleLL * ref, int data)
{
	LinkNode * node = getLinkNode(data);
	if (ref->head == NULL)
	{
		ref->head = node;
	}
	else
	{
		// Append the node at last position
		ref->tail->next = node;
	}
	ref->tail = node;
}
// Display linked list element
void display(SingleLL * ref)
{
	if (ref->head == NULL)
	{
		printf("\n Empty linked list");
		return;
	}
	LinkNode * temp = ref->head;
	// iterating linked list elements
	while (temp != NULL)
	{
		printf(" %d →", temp->data);
		// Visit to next node
		temp = temp->next;
	}
	printf(" NULL\n");
}
// This are perform the linked list rotation
void rotation(SingleLL * ref, int k)
{
	// Define some auxiliary variable
	LinkNode * auxiliary = ref->head;
	int count = 0;
	// Count number of node in linked list
	while (auxiliary != NULL)
	{
		// visit to next node
		auxiliary = auxiliary->next;
		count++;
	}
	if (count <= 1)
	{
		// When have less than 2 nodes in linked list
		return;
	}
	// Get actual rotation
	count = k % count;
	if (count == 0)
	{
		// When actual linked list are not affected
		return;
	}
	auxiliary = ref->head;
	// Find the rotational node
	while (count > 1)
	{
		// Visit to next node
		auxiliary = auxiliary->next;
		count--;
	}
	// Connecting the last node to first node of linked list
	ref->tail->next = ref->head;
	// Set new last node
	ref->tail = auxiliary;
	// Set new head
	ref->head = auxiliary->next;
	// Set that there is no node after of tail
	ref->tail->next = NULL;
}
// Handles the request to perform rotation
// k is indicate node rotation
void clockwiseRotation(SingleLL * ref, int k)
{
	if (k <= 0)
	{
		// When invalid given k
		return;
	}
	if (ref->head == NULL)
	{
		printf("\n Empty Linked List");
		return;
	}
	// Display given linked list
	printf(" Before rotate \n");
	printf(" Linked List : ");
	display(ref);
	printf(" Given k : %d", k);
	// Perform rotation
	rotation(ref,k);
	// Display resultant linked list
	printf("\n After rotate \n");
	printf(" Linked List : ");
	display(ref);
	printf("\n");
}
int main()
{
	SingleLL * sll1 = getSingleLL();
	SingleLL * sll2 = getSingleLL();
	// First linked list
	// 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	addNode(sll1, 1);
	addNode(sll1, 2);
	addNode(sll1, 3);
	addNode(sll1, 4);
	addNode(sll1, 5);
	addNode(sll1, 6);
	addNode(sll1, 7);
	addNode(sll1, 8);
	// Second linked list
	// 4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
	addNode(sll2, 4);
	addNode(sll2, 9);
	addNode(sll2, 7);
	addNode(sll2, 3);
	addNode(sll2, 8);
	addNode(sll2, 6);
	addNode(sll2, -2);
	// Test case
	clockwiseRotation(sll1, 3);
	clockwiseRotation(sll2, 18);
	return 0;
}

Output

 Before rotate
 Linked List :  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
 Given k : 3
 After rotate
 Linked List :  4 → 5 → 6 → 7 → 8 → 1 → 2 → 3 → NULL

 Before rotate
 Linked List :  4 → 9 → 7 → 3 → 8 → 6 → -2 → NULL
 Given k : 18
 After rotate
 Linked List :  8 → 6 → -2 → 4 → 9 → 7 → 3 → NULL




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment