Reverse Nodes In Even Length Groups

Try to solve the Reverse Nodes in Even Length Groups problem.

We'll cover the following

Statement#

Given the head of a linked list, the nodes in it are assigned to each group in a sequential manner. The length of these groups follows the sequence of natural numbers. Natural numbers are positive whole numbers denoted by (1,2,3,4...)(1,2,3,4...).

In other words:

  • The 1st1^{st} node is assigned to the first group.

  • The 2nd2^{nd} and 3rd3^{rd} nodes are assigned to the second group.

  • The 4th4^{th}, 5th5^{th}, and 6th6^{th} nodes are assigned to the third group, and so on.

Your task is to reverse the nodes in each group with an even number of nodes and return the head of the modified linked list.

Note: The length of the last group may be less than or equal to 1 + the length of the second to the last group.

Constraints:

  • 1 ≤\leq Number of nodes ≤\leq 500
  • 0 ≤\leq LinkedListNode.data ≤\leq 10310^{3}

Examples#

You can understand the problem a little better with the help of the illustration below:

Created with Fabric.js 3.6.6 Ouput Sample example 1 Input 1 1 0 6 1 0 1 6

1 of 3

Created with Fabric.js 3.6.6 Ouput Input Sample example 2 3 2 0 6 5 3 0 2 5 6

2 of 3

Created with Fabric.js 3.6.6 Input Ouput Sample example 3 5 2 6 3 9 1 7 3 8 4 5 6 2 3 9 1 4 7 3 8

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Reverse Nodes in Even Length Groups

1

What is the output if the following linked list is provided as input?

4 → 3 → 0 → 5 → 1 → 2 → 7 → 8 → 6

A)

3 → 4 → 2 → 1 → 5 → 0 → 7 → 8 → 6

B)

3 → 4 → 5 → 0 → 2 → 1 → 8 → 7 → 6

C)

4 → 0 → 3 → 5 → 1 → 2 → 8 → 7 → 6

D)

4 → 0 → 3 → 5 → 1 → 2 → 7 → 8 → 6

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Reverse Nodes in Even Length Groups

Initialize a variable, l, to keep track of the length of the groups. Set it to 2, since the first group is of odd length, i.e., 1.

Iterate the linked list and keep track of the nodes that are successfully traversed in the current group using a variable n.

If there is a group with an odd number of nodes, move forward.

Otherwise, reverse the nodes present in the current group by using three variables, i.e., prev, curr, and reverse to reverse the direction of the next pointers of the nodes.

Increment l by 1 and repeat the process until all nodes of the linked list have been traversed completely.

Finally, return the head of this modified linked list.

Try it yourself#

Implement your solution in main.py in the following coding playground. We have provided some useful code templates in the other file that you may build on to solve this problem.

Python
main.py
linked_list_node.py
linked_list.py
linked_list_reversal.py
linked_list_traversal.py
Input #1
%0 node_01 1 node_11 2 node_01->node_11 node_21 3 node_11->node_21 node_31 4 node_21->node_31
Visualization for Input #1
Reverse Nodes in Even Length Groups

Solution: Reverse Linked List

Solution: Reverse Nodes in Even Length Groups