How to Solve Reverse Nodes in k-Group

Written By
Adam Bhula

Reverse Nodes in k-Group Introduction

The Reverse Nodes in k-Group problem asks us to reverse the nodes of the given linked list k at a time and return the modified list. This problem can be solved using a recursive approach.

Reverse Nodes in k-Group Problem

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example Inputs and Outputs

Example 1

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Reverse Nodes in k-Group Solutions

To solve this problem, we use a recursive approach. We go through the linked list, considering k nodes at a time. If there are fewer than k nodes remaining, we leave them as they are without reversing. However, when we have k nodes, we reverse them by changing their next pointers. This reversal process involves carefully keeping track of the previous and next pointers.

Once we reverse the k nodes, the head of the reversed portion becomes the last node of the original k nodes, and we update its next pointer to point to the result of reversing the remaining list. We repeat this process until we reach the end of the linked list. By doing this, we gradually reverse the linked list in groups of k nodes.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head, k):
    if not head or not head.next:
        return head

    count = 0
    curr = head

    # Check if the number of nodes is a multiple of k
    while curr and count < k:
        curr = curr.next
        count += 1

    if count < k:  # Number of nodes is less than k
        return head

    # Reverse the first k nodes
    curr = head
    prev = None
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # Recursively reverse the remaining list
    head.next = reverseKGroup(curr, k)

    return prev

# Driver code and test cases
# Test Case 1: Reverse groups of 2 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 2 -> 1 -> 4 -> 3 -> 5 -> None
head1 = ListNode(1)
head1.next = ListNode(2)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(4)
head1.next.next.next.next = ListNode(5)
k1 = 2
reversed_list1 = reverseKGroup(head1, k1)
while reversed_list1:
    print(reversed_list1.val, end=" -> ")
    reversed_list1 = reversed_list1.next

# Test Case 2: Reverse groups of 3 nodes
# Input: 1 -> 2 -> 3 -> 4 -> 5 -> None
# Output: 3 -> 2 -> 1 -> 4 -> 5 -> None
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
head2.next.next.next = ListNode(4)
head2.next.next.next.next = ListNode(5)
k2 = 3
reversed_list2 = reverseKGroup(head2, k2)
while reversed_list2:
    print(reversed_list2.val, end=" -> ")
    reversed_list2 = reversed_list2.next

Time/Space Complexity Analysis

  • Time Complexity: O(N), where n is the number of nodes in the linked list. In the worst case, we need to reverse all the nodes in the linked list. It's important to note that the algorithm performs a constant amount of work per node, and the number of nodes processed remains the same regardless of the group size k. So, the time complexity does not depend on the value of k.
  • Space Complexity: O(1), because regardless of the size of the linked list or the group size, the amount of addition space remains used constant.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.