Educative: Interactive Courses for Software Developers

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...)$ .

In other words:

The $1^{st}$ node is assigned to the first group.
The $2^{nd}$ and $3^{rd}$ nodes are assigned to the second group.
The $4^{th}$ , $5^{th}$ , and $6^{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 10^3$

Solution#

We need to reverse the groups in the linked list with an even number of nodes. For this, we use the in-place reversal of the linked list. The first task is to identify these groups, and once they are identified, we can safely reverse the nodes present in these groups. Once all nodes are processed, we return the head of the modified linked list.

Following is the algorithm we will follow to achieve the solution to this problem:

We first initialize two variables, prev and group_len, to point to the current group’s previous node and the current group’s length, respectively. We will set group_len to 2 at the beginning, as the first node of the linked list cannot be reversed since its group’s length is odd, i.e., 1.
Iterate the nodes of the linked list, and in each iteration, we set a variable node to track the current node and num_nodes to account for the number of nodes in the current group.
Next, we check the current group and count the nodes in it using num_nodes. If the current group’s length is odd, it means that the group needs to be skipped, so the prev pointer is moved to the current node to start the next group’s processing.
For groups with an even number of nodes, we will follow this procedure to reverse the nodes:
- We maintain three pointers, i.e., prev, curr, and reverse to point to the node immediately before the current group, to the first node of the current group, and to the next node of the current group, respectively.
- We loop over the length of the group to reverse the nodes. For each node in the group, we save the reference to the next node, curr_next, since we will change curr’s next pointer.
- Next, make curr.next point to the previous node reverse. This step effectively reverses the pointer direction.
- Move reverse to the current node curr because it will be the next node in the reversed group.
- Then, move curr to the next node in the original order curr_next to continue the reversal process.
- Once the whole group is reversed, we update the prev.next to the last node and prev to the first node of the current group.

We keep on doing this until all the nodes of the linked list have been processed. Let’s look at the illustration below to better understand the solution:

main.py

linked_list_node.py

linked_list.py

print_list.py

from linked_list import LinkedList
from print_list import print_list_with_forward_arrow
def reverse_even_length_groups(head):
    prev = head  
    l = 2
    while prev.next:
        node = prev
        n = 0
        for i in range(l):
            if not node.next:
                break
            n += 1
            node = node.next
        if n % 2:  
            prev = node
        else:      
            reverse = node.next
            curr = prev.next
            for j in range(n):
                curr_next = curr.next
                curr.next = reverse
                reverse = curr
                curr = curr_next
            prev_next = prev.next
            prev.next = node
            prev = prev_next
        l += 1

Enter to Rename, Shift+Enter to Preview

Reverse Nodes In Even Length Groups

Solution: Reverse Nodes in Even Length Groups

Statement#

Solution#

Time complexity#

Space complexity#