Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given a single linked list, rotate the list counterclockwise by k nodes. Where k is a given positive integer. For example, if a given list is 10->20->30->40->50->60 and k is 4, the list should be modified to 50->60->10->20->30- >40. Suppose k is less than the number of nodes in the list.

Method 1: To rotate the list, we need to change next to NULL on the KTH node, next on the last node to the previous head node, and finally head to the (k+1) node. So we need to know three nodes: the KTH node, the (k+1) node, and the last node. Iterate through the list from the beginning and stop at the KTH node. Stores a pointer to the KTH node. We can use kthNode->next to get the (k+1) node. Continue to the end and store a pointer to the last node. Finally, change the pointer as described above.

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

void rotate(Node** head_ref, int k)
{
	if (k == 0)
		return;

	Node* current = *head_ref;

	int count = 1;
	while(count < k && current ! =NULL) {
		current = current->next;
		count++;
	}

	if (current == NULL)
		return;

	Node* kthNode = current;

	while(current->next ! =NULL)
		current = current->next;

	current->next = *head_ref;
	*head_ref = kthNode->next;
	kthNode->next = NULL;
}

void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void printList(Node* node)
{
	while(node ! =NULL) {
		cout << node->data << ""; node = node->next; }}int main(void)
{

	Node* head = NULL;
	for (int i = 60; i > 0; i -= 10)
		push(&head, i);

	cout << "Given linked list \n";
	printList(head);
	rotate(&head, 4);

	cout << "\nRotated Linked list \n";
	printList(head);

	return (0);
}
Copy the code

Output:

Given linked list
10  20  30  40  50  60
Rotated Linked list
50  60  10  20  30  40
Copy the code

Time complexity: O(n), where n is the number of nodes in the linked list. The code traverses the list only once. If you find anything incorrect, or if you would like to share more information about the topic above, please comment.

Method 2: Rotate the list by K. We can loop the list first and then move the head node k-1 step forward so that the (K-1) node is next to empty and starts with the KTH node.

#include <bits/stdc++.h>
using namespacestd; ,class Node {
public:
	int data;
	Node* next;
};

void rotate(Node** head_ref, int k)
{
	if (k == 0)
		return;
	Node* current = *head_ref;
	while(current->next ! =NULL)
		current = current->next;

	current->next = *head_ref;
	current = *head_ref;
	for (int i = 0; i < k - 1; i++)
		current = current->next;
	*head_ref = current->next;
	current->next = NULL;
}

void push(Node** head_ref, int new_data)
{
	Node* new_node = new Node(a); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; }void printList(Node* node)
{
	while(node ! =NULL) {
		cout << node->data << ""; node = node->next; }}int main(void)
{
	Node* head = NULL;

	for (int i = 60; i > 0; i -= 10)
		push(&head, i);

	cout << "Given linked list \n";
	printList(head);
	rotate(&head, 4);

	cout << "\nRotated Linked list \n";
	printList(head);

	return (0);
}
Copy the code

Output:

Given linked list 
10 20 30 40 50 60 
Rotated Linked list 
50 60 10 20 30 40
Copy the code

🥇 past quality articles

Singly linked list data structure of the chain table from the introduction of | first set of singly linked list data structure linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure of the fourth set of singly linked list data structure to delete a given location linked list node | the fifth set Singly linked list data structure of the check method of array and list | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2 singly linked list data structure of the length of the chain table lookup (iteration and recursion) | 7 sets of singly linked list data structure of switching nodes in the list without exchanging data | 8 sets Singly linked list data structure of the inversion list | 9 sets of singly linked list data structure of merging two sorted lists | 10 sets of singly linked list data structure of the list of merge sort | 11 sets of singly linked list data structure with the size of a given set of inversion list | detection of 12 sets of singly linked list data structure and delete cycle | 13 set in the list Singly linked list data structure will represent the list of the two Numbers together | 14 sets

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.