Reversing a singly linked list of n elements in group of k(k-reverse a linked list)— Coding Question asked by Google, Amazon, Adobe

Problem Statement:

In a linked list of n number of nodes, reverse the nodes of the list k at a time, and return modified list. Here k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, may be reversed in the leftover group.

Don’t alter the values in the list’s nodes, only nodes themselves may be changed. Keep number of nodes n and the reversal order k is decided by the user. The input of values at nodes is also decided by the user.

Input format :

Number of nodes in linked list, elements of linked list and the number of nodes in a group to be reversed.

Output format :

Prints the linked list in order after “k-reversal”.

Sample Input:

11
1->2->3->4->5->6->7->8->9->10->11
3

Sample Output:

3->2->1->6->5->4->9->8->7->11->10

(Note that if in the end there is a group left with b<k elements, then it shall be reversed in the group of b elements itself.)

Approach:

First, a struct for node is declared, as we make node a composite datatype of data and the address of next node. This may be declared as node class too instead of struct. We are using struct as both the variables are to be kept public by default and syntax remains easier whenever we want to declare a node.

Then to declare the linked list, we make a class. In it we have different functions to make a linked list(adding a node). In order to add a node, we use a temporary node.

After that, tail is assigned to the temp node.

This is the general approach we shall use to make the linked list as we want all the elements to be assigned by user input.

To k-reverse the linked list, initially a current node is taken as head node. Like ordinary reversal operation, a first node and previous node has been declared to denote the first node of k-node group and previous node defines node previous to the current node. It has been depicted graphically for first two iterations below.

And like this, in each iteration, prev_first is reallocated and the curr is passed to next group

Time complexity: O(n)

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.