Reverse a Linked List in groups of given size

Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list.

Reverse a Linked List in groups of given size


Example 1:

Input:

LinkedList: 1->2->2->4->5->6->7->8

K = 4

Output: 4 2 2 1 8 7 6 5 

Explanation: 

The first 4 elements 1,2,2,4 are reversed first 

and then the next 4 elements 5,6,7,8. Hence, the 

resultant linked list is 4->2->2->1->8->7->6->5.


Example 2:

Input:

LinkedList: 1->2->3->4->5

K = 3

Output: 3 2 1 5 4 

Explanation: 

The first 3 elements are 1,2,3 are reversed 

first and then elements 4,5 are reversed.Hence, 

the resultant linked list is 3->2->1->5->4.



c++ implementation:

struct node *reverse (struct node* head, int k)

{

struct node* current = head;

struct node* next = NULL;

struct node* prev = NULL;

int count = 0; 

while (current != NULL && count < k)

// reversing k elements :

{

next = current->next;             // marking next node

current->next = prev;             // reversing link

prev = current;                   // updating prev

current = next;                   // updating current

count++;

}

if (next != NULL)       // checking if there are nodes ahead

     head->next = reverse(next, k);    // reversing those recursively

    

return prev;            // returning new head

}

Time Complexity: O(n)  
darkmode