Reverse linked list grouping by given size using C++
In this article, we deal with a singly linked list and the task is to reverse the list in groups of k. For example -
Input: 1->2->3->4->5->6->7->8->NULL, K = 3 Output: 3->2->1->6->5->4->8->7->NULL Input: 1->2->3->4->5->6->7->8->NULL, K = 5 Output: 5->4->3->2->1->8
For this problem, one approach that comes to mind is to tail the list and reverse the list when the size of the sublist reaches k and continue.
Methods to find solutions
With this method, we usually iterate through the list and keep a counter to count the number of elements in the sublist. When the counter reaches a count of k, we invert that part.
Example
#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* curr = head; Node* next = NULL; Node* prev = NULL; int count = 0; while (curr != NULL && count < k) { // we reverse the list till our count is less than k next = curr->next; curr->next = prev; prev = curr; curr = next; count++; } if (next != NULL) // if our link list has not ended we call reverse function again head->next = reverse(next, k); return prev; } void push(Node** head_ref, int new_data) { // function for pushing data in the list Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { // function to print linked list while (node != NULL) { cout << node->data << " "; node = node->next; } cout << "\n"; } int main() { Node* head = NULL; int k = 3; // the given k 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 << "Original list \n"; printList(head); head = reverse(head, k); // this function will return us our new head cout << "New list \n"; printList(head); return (0); }
Output
Original list 1 2 3 4 5 6 7 8 New list 3 2 1 6 5 4 8 7
The time complexity of the above method is O(N), where N is the size of the given list, and This method works recursively. This approach also works for higher constraints.
Explanation of the above code
In this method we will iterate through the array and keep reversing it until our counter variable is less than k. When the counter reaches the value of k, we call another inversion function to connect the last node of this sublist to the first node of the next inverted sublist. This is done recursively.
Conclusion
In this article, we solved the problem of reversing a linked list by groups of a given size using recursion. We also learned a C program to solve this problem and a complete method to solve this problem (Normal). We can write the same program in other languages such as C, java, python and other languages. We hope this article was helpful to you.
The above is the detailed content of Reverse linked list grouping by given size using C++. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

typedef struct is used in C language to create structure type aliases to simplify the use of structures. It aliases a new data type to an existing structure by specifying the structure alias. Benefits include enhanced readability, code reuse, and type checking. Note: The structure must be defined before using an alias. The alias must be unique in the program and only valid within the scope in which it is declared.

real is the data type used to represent double-precision floating-point numbers in C language. It occupies 8 bytes, has a precision of about 15 decimal places, and the range is [-1.7976931348623157e+308, 1.7976931348623157e+308].

The complex type is used to represent complex numbers in C language, including real and imaginary parts. Its initialization form is complex_number = 3.14 + 2.71i, the real part can be accessed through creal(complex_number), and the imaginary part can be accessed through cimag(complex_number). This type supports common mathematical operations such as addition, subtraction, multiplication, division, and modulo. In addition, a set of functions for working with complex numbers is provided, such as cpow, csqrt, cexp, and csin.

The restrict keyword is used to inform the compiler that a variable can only be accessed by a pointer, preventing undefined behavior, optimizing code and improving readability: Preventing undefined behavior when multiple pointers point to the same variable. To optimize code, the compiler uses the restrict keyword to optimize variable access. Improves code readability by indicating that variables can only be accessed by a pointer.

In C language, there are two ways to implement the exponentiation operation: use the pow() function to calculate the power of the second parameter of the first parameter. Define a custom power function, which can be implemented recursively or iteratively: the recursive method continues to double the power until it is 0. The iterative method uses a loop to multiply the base one by one.

In C language, methods for handling scanf function errors include: 1. Check the format string; 2. Check the input; 3. Check the return value; 4. Set the error flag; 5. Use the error handling function; 6. Use custom errors deal with. To prevent errors, use the correct data types, carefully validate input, check return values, and handle potential errors in your program.

_Bool represents Boolean type in C language. It is a simple data type that contains only two values, true or false. It is used to represent the results of conditions or logical expressions. It usually occupies 1 byte of memory and can only store true or false. false value.

reg is the keyword used for registers in C language and is used to declare pointer variables pointing to registers. Syntax: register data_type *var_name; where data_type is the data type stored in the register, and var_name is the name of the pointer variable. The value in the register can be accessed by dereferencing the pointer, but please note that the available registers vary between platforms and compilers.
