Reverse Alternate K nodes

Easy
0/40
Average time to solve is 10m
profile
Contributed by
14 upvotes
Asked in companies
AdobeIntuitSalesforce

Problem statement

You are given a Singly Linked List of integers and a positive integer 'K'. Modify the linked list by reversing every alternate 'K' nodes of the linked list.

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).
Note: 
If the number of nodes in the list or in the last group is less than 'K', just reverse the remaining nodes.
Example: 
Linked list: 5 6 7 8 9 10 11 12
K: 3 

Output: 7 6 5 8 9 10 12 11

We reverse the first 'K' (3) nodes and then skip the next 'K'(3) nodes. Now, since the number of nodes remaining in the list (2) is less than 'K', we just reverse the remaining nodes (11 and 12).
Note: 
You need to reverse the first 'K' nodes and then skip the 'K' nodes and so on. 5 6 7 10 9 8 11 12 is not the correct answer for the given linked list.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T', the number of test cases.

The first line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of every test case contains the positive integer ‘K’.
Output Format: 
For every test case, return the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= N
-10^3 <= data <= 10^3 and data != -1

Time Limit: 1 sec
Sample Input 1:
1 
1 2 3 4 5 6 7 -1
2
Sample Output 1:
2 1 3 4 6 5 7 -1
Explanation of sample input 1:
In the given linked list, we have to reverse the first two nodes, then skip two nodes, and so on… until all the nodes are processed in the same way.
The modified linked list after the above process is 2 1 3 4 6 5 7 -1
Sample Input 2:
2
5 10 -6 4 7 -1 
3 
10 20 30 40 50 -1
1
Sample Output 2:
-6 10 5 4 7 -1
10 20 30 40 50 -1
Hint

Can we use recursion to solve this problem?

Approaches (2)
Recursion

The idea is very simple. We will process 2 * ‘K’ nodes at a time. Firstly, we will reverse the first ‘K’ nodes of the linked list and then we will skip the next ‘K’ nodes. We will do this recursively for the remaining linked list.

 

Algorithm:

  • If the node does not exist, simply return ‘NULL’.
  • Head is pointing to the first node of the linked list.
  • If there are less than ‘K’ nodes, just reverse them and return the reversed linked list. Else reverse the first ‘K’ nodes of the linked list.
  • After reversing the ‘K’ nodes, the head points to the ‘K’th node and the ‘K’th node in the original linked list will become the new head.
  • To connect the reversed part with the remaining part of the linked list, update the next of the head to (‘K’ + 1)th node.
  • As we don’t have to reverse the next ‘K’ nodes, we will skip them.
  • Now, recursively modify the rest of the linked list and link the two sub-linked lists.
  • Return the new head of the linked list.
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

Since each node of the linked list is traversed exactly once, the final time complexity is O(N). 

Space Complexity

O(N / (2 * K)), where ‘N’ is the number of nodes in the linked list and ‘K’ is the given positive integer. 

 

In each recursive step, we are processing (2 * K) nodes of the linked list. Thus, O(N / (2 * K)) is the total recursion stack space used by the algorithm. 

Code Solution
(100% EXP penalty)
Reverse Alternate K nodes
Full screen
Console