Reverse Nodes in k-Group

Try to solve the Reverse Nodes in k-Group problem.

We'll cover the following

Statement#

The task is to reverse the nodes in groups of kk in a given linked list, where kk is a positive integer, and at most the length of the linked list. If any remaining nodes are not part of a group of kk, they should remain in their original order.

It is not allowed to change the values of the nodes in the linked list. Only the order of the nodes can be modified.

Note: Use only O(1)O(1) extra memory space.

Constraints:

Let n be the number of nodes in a linked list.

  • 1≤1 \leq k ≤\leq n ≤500\leq 500
  • 0≤0 \leq Node.value ≤1000\leq 1000

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

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

Reverse Nodes in k-Group

1

What is the output if the following head of the linked list and value of kk are given as input?

head → 8 → 0 → 6 → 1 → 0 → 7 → 8 → 7 → 5 → 3 → 5 → 2 → 4 → 9 → NULL

k = 3

A)

head → 1 → 0 → 7 → 8 → 0 → 6 → 3 → 5 → 2 → 8 → 7 → 5 → 4 → 9 → NULL

B)

head → 7 → 0 → 1 → 6 → 0 → 8 → 2 → 5 → 3 → 5 → 7 → 8 → 4 → 9 → NULL

C)

head → 6 → 0 → 8 → 7 → 0 → 1 → 5 → 7 → 8 → 2 → 5 → 3 → 4 → 9 → NULL

D)

head → 8 → 0 → 0 → 1 → 6 → 7 → 8 → 7 → 5 → 3 → 5 → 9 → 4 → 2 → NULL

Question 1 of 40 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.

Drag and drop the cards to rearrange them in the correct sequence.

Use a pointer to try to traverse kk nodes in the linked list.

If the pointer successfully traverses a group of kk nodes, reverse this group.

Reconnect the reversed group of kk nodes with the rest of the linked list.

Repeat this process until less than kk or no nodes are left in the linked list.

Try it yourself#

Implement your solution in main.py in the following coding playground. You’ll need the provided supporting code to implement your solution. We’ve provided some useful code templates that you may build on to solve this problem.

Python
main.py
linked_list_node.py
linked_list.py
linked_list_traversal.py
linked_list_reversal.py
Input #1
Input #2
%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 node_41 5 node_31->node_41
Visualization for Input #1
Reverse Nodes in k-Group

Solution: Reverse Nodes in Even Length Groups

Solution: Reverse Nodes in k-Group