Reverse List In K Groups
You are given a linked list of 'N' nodes and an integer 'K'. You have to reverse the given linked list in groups of size K i.e if the list contains x nodes numbered from 1 to x, then you need to reverse each of the groups (1,K),(K+1,2*K), and so on.

For example, if the list is [1, 2, 3, 4, 5, 6] and K = 2, then the new list will be [2, 1, 4, 3, 6, 5].

Note:

1. In case the number of elements in the last cannot be evenly divided into groups of size k, then just reverse the last group(with any size). For example if the list is 1 2 3 4 5 and K = 3, then the answer would be 3 2 1 5 4. 2. All the node values will be distinct.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then T test cases follow. The first line of each test case contains a Linked list whose elements are separated by space and the linked list is terminated by -1. The second line of each test case contains an integer K.

Output Format:

For each test case print the elements of modified linked list separated by space.. The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Reverse List In K Groups

You are given a linked list of 'N' nodes and an integer 'K'. You have to reverse the given linked list in groups of size K i.e if the list contains x nodes numbered from 1 to x, then you need to reverse each of the groups (1,K),(K+1,2*K), and so on.

For example, if the list is [1, 2, 3, 4, 5, 6] and K = 2, then the new list will be [2, 1, 4, 3, 6, 5].

Note:

1. In case the number of elements in the last cannot be evenly divided into groups of size k, then just reverse the last group(with any size). For example if the list is 1 2 3 4 5 and K = 3, then the answer would be 3 2 1 5 4.

2. All the node values will be distinct.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then T test cases follow.

The first line of each test case contains a Linked list whose elements are separated by space and the linked list is terminated by -1.

The second line of each test case contains an integer K.

Output Format:

 For each test case print the elements of  modified linked list separated by space..

The output of each test case will be printed in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100   
1 <= N <= 10^4
1 <= K <= 10^4

Time Limit: 1sec

Accepted Answer

Step 1 : We first traverse till kth node, keep track of next node and call function to reverse the first k nodes
Step 2 : For reversing we use 3 pointers to reverse the linkedlist

Accepted Answer

Recursive Approach

We can use recursion to solve this problem.
The main idea is to reverse the first ‘K’ nodes by ourselves and let the recursive function reverse the rest of the linked list.
Let reverseList() be the recursive function which takes the head of the linked list and ‘K’ as the parameters.
Now we can iteratively reverse the first ‘K’ nodes of the linked list.
And then if we still have some nodes left in the linked list, then we can call reverseList(), until the nodes are exhausted.

Space Complexity: O(n)Explanation:

O(N), Stack space for recursive calls of ‘N’ nodes of the linked list.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the Linked List.

Accepted Answer

Iterative Approach

Since we have to optimize on space, instead of using recursion we can use some pointers to create the links between the different sets of 'K' nodes.
First of all we have to create some pointers to keep the track of a current set of ‘K’ nodes and the previously modified linked list and curr denotes the current node that we are on.
Let ‘prev’ denote the previous pointer, a ‘tail’ pointer which keeps the track of the last node of the ‘K’ set of nodes and ‘join’ pointer points to the current set of nodes which we have to join to the modified linked list.
Now keep on traversing the list until we reach the end and do the following:
- Let ‘join’ = ‘curr’ and ‘prev’ = NULL. Now reverse the ‘K’ set of nodes in the linked list.
- If we have not assigned the ‘newHead’, then assign the ‘newHead’ to the ‘prev’ pointer.
- If we already have the tail of the linked list, then the next of tail should point to the ‘prev’ i.e. ‘tail’ -> ‘next’ = ‘prev’.
- Now update the ‘tail’ to the last node of the K-reversed linked list i.e. ‘tail’ = ‘join’.
For example, let the linked list be 1 2 3 4 and k = 2.
Initially, we will have ‘curr’ pointing to the ‘head’ of the list. Until we don’t reach the end, we do the following steps:
- Setting ‘join’ = ‘curr’ and ‘prev’ = NULL and hence join will point to 1 initially. After reversing the first ‘K’ nodes, our prev will point to 2.
- Now we will assign the tail to join because the join was initially pointing to the head and after reversing the ‘K’ nodes it will be pointing to the last node of the current set of nodes.
- We will repeat the same process again and hence we will get the required output.

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the Linked List.

You are given a linked list of 'N' nodes and an integer 'K'. You have to reverse the given linked list in groups of size K i.e if the list contains x nodes numbered from 1 to x, then you need to reverse each of the groups (1,K),(K+1,2*K), and so on.

For example, if the list is [1, 2, 3, 4, 5, 6] and K = 2, then the new list will be [2, 1, 4, 3, 6, 5].

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Josh Technology Group Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern