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

Given a linked list, write a function that reverses each k node (where k is the input to the function).

Example:

Input: 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL, K = 3 output: 3 – > 2 – > 1 – > 6 – > 5 – > 4-7 8 – > > > NULL input: 1 – > 2 – > 3 – > 4 – > 5 – > 6-7-8 – > > > NULL, K = 5 output: 5->4->3-> 2->1->8->7->6->NULL

Algorithm: Reverse (head, K)

  • Reverse the first sublist of size K. Track the next node and the previous node while backing up. Let the pointer to the next node benext, the pointer to the previous node isprev. Please refer to theThis postTo reverse the list of links.
  • head->next = reverse(next, k)(Recursively calls the rest of the list and links the two sublists)
  • returnprev(prevBecome the new head of the list (seeThis articleIterative method diagram of

Here is an implementation of the above method:

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

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

Node* reverse(Node* head, int k)
{
	if(! head)return NULL;
	Node* current = head;
	Node* next = NULL;
	Node* prev = NULL;
	int count = 0;

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

	if(next ! =NULL)
		head->next = reverse(next, k);

	return prev;
}

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(a)
{
	Node* head = NULL;
	push(&head, 9);
	push(&head, 8);
	push(&head, 7);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	push(&head, 2);
	push(&head, 1);

	cout << "Given linked list \n";
	printList(head);
	head = reverse(head, 3);

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

	return (0);
}
Copy the code

Output:

Given Linked List
1 2 3 4 5 6 7 8 9 
Reversed list
3 2 1 6 5 4 9 8 7 
Copy the code

Complexity analysis:

  • Time complexity: O(n). The list is traversed only once, and it has ‘n’ elements.

  • Auxiliary space: O(N/K). For each list of size N, n/ K or (n/k)+1 calls are made during recursion.

    🥇 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 in the linked list of merge sort | 11 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 📑.