Reverse Nodes in k-Group - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

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

› Output: [2,1,4,3,5]

💡 Note: Reverse first 2 nodes: [1,2] becomes [2,1]. Reverse next 2 nodes: [3,4] becomes [4,3]. Node 5 remains as is since it's incomplete group.

Example 2 — Perfect Groups

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

› Output: [3,2,1,6,5,4]

💡 Note: Reverse first 3 nodes: [1,2,3] becomes [3,2,1]. Reverse next 3 nodes: [4,5,6] becomes [6,5,4]. All nodes form complete groups.

Example 3 — Single Node

$ Input: head = [1], k = 1

› Output: [1]

💡 Note: When k=1, no reversal needed. Return original list unchanged.

Constraints

The number of nodes in the list is n.
1 ≤ k ≤ n ≤ 5000
0 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list [1,2,3,4,5] with k=2

Process

Reverse complete groups of k nodes

Output

Result: [2,1,4,3,5]

Key Takeaway

🎯 Key Insight: Only reverse complete groups of k nodes, leaving incomplete groups at the end unchanged

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to reverse each complete group of k nodes in-place using three pointers, leaving incomplete groups unchanged. The optimal approach uses recursion with O(1) extra space and O(n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ In-Place Reversal	O(n)	O(1)	Reverse each group directly in the linked list using three pointers
Array Conversion Approach	O(n)	O(n)	Convert linked list to array, reverse every k elements, rebuild list

In-Place Reversal — Algorithm Steps

Step 1: Check if k nodes remain
Step 2: Reverse the k nodes using three pointers
Step 3: Connect reversed group to rest of list

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Pointers

Initialize prev=null, current=head

Reverse Links

Reverse k nodes using three pointers

Connect Groups

Link reversed group to next part

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current = current->next;
        current->val = arr[i];
        current->next = NULL;
    }
    return head;
}

int listToArray(struct ListNode* head, int* arr) {
    int size = 0;
    struct ListNode* current = head;
    while (current) {
        arr[size++] = current->val;
        current = current->next;
    }
    return size;
}

int hasKNodes(struct ListNode* node, int k) {
    int count = 0;
    while (node && count < k) {
        node = node->next;
        count++;
    }
    return count == k;
}

struct ListNode* solution(struct ListNode* head, int k) {
    if (!head || k == 1) return head;
    
    // Check if we have at least k nodes
    if (!hasKNodes(head, k)) {
        return head;
    }
    
    // Reverse first k nodes
    struct ListNode* prev = NULL;
    struct ListNode* current = head;
    struct ListNode* nextGroup = NULL;
    
    for (int i = 0; i < k; i++) {
        nextGroup = current->next;
        current->next = prev;
        prev = current;
        current = nextGroup;
    }
    
    // head now points to the last node of first group
    // Recursively process remaining nodes
    head->next = solution(nextGroup, k);
    
    return prev; // new head
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int headArr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token) {
        headArr[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    struct ListNode* head = arrayToList(headArr, size);
    struct ListNode* result = solution(head, k);
    
    int resultArr[1000];
    int resultSize = listToArray(result, resultArr);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        if (i > 0) printf(",");
        printf("%d", resultArr[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n nodes, each node visited once

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for pointers

✓ Linear Space

78.0K Views

Medium-High Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

In-Place Reversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler