Linked list reversed in groups of K nodes

Question

Initially, the interviewer asked the question to reverse the linked list which I solved easily.
Now he said to reverse the list in groups of K nodes.

for example, if the list is [1,2,3,4,5,6] and K=4 then o/p = [4,3,2,1,5,6].. So I have modified the existing solution to achieve it but still, it gives the output of the whole list reversed (i.e [6,5,4,3,2,1]). see the below program. It might be some minor change needed but I couldn't figure out it. Can anyone help where is issue?

ListNode *reverseKGroup(ListNode *head, int k) 
{
    if (k == 0 || k == 1)
        return head;

    if (head == NULL)
        return NULL;

    int counter = 0;
    ListNode *fastPtr = head;
    ListNode *currentPtr = head;
    ListNode *nextPtr = NULL;
    ListNode *prevPtr = NULL;
        
    while (fastPtr)
    {
        counter++;

        //one chain formed from list, reverse it
        if (counter == k)
        {
            fastPtr = fastPtr->next;
            
            while (counter)
            {
                nextPtr = currentPtr->next;
                currentPtr->next = prevPtr;
                prevPtr = currentPtr;
                currentPtr = nextPtr;
                counter--;
            }

            //last node
            if (currentPtr->next == NULL)
            {
                currentPtr->next = prevPtr;
                prevPtr = currentPtr;
                break;
            }
        }
        else
        {
            fastPtr = fastPtr->next;
        }
    }
    
    return prevPtr;
}

Answer 1

Your approach is OK, but you do not link the reversed list fragments correctly:

• you can factorize fastPtr = fastPtr->next; as it is performed in both branches of the if statement.

• the test for the last node is bogus: if (currentPtr->next == NULL) will dereference a null pointer if the list length is a multiple of k.

• you should instead keep a pointer to the place where to store the head of the reversed list fragment. At the start of the loop this pointer points to the variable head, and after each fragment reversal, it should point to the next member of the first node of the fragment before reversal, which is the value of CurrentNode at the start of the reversing loop.

With these small modifications, your code runs fine.

Note that this question is tricky. If the interviewer requires from you to solve it interactively, they are probably interested in your approach to problem solving. Constructing an effective and elegant solution in less than half an hour would be very good.

Here is the modified version with a testbed:

#include <stdio.h>

typedef struct ListNode {
    struct ListNode *next;
    int data;
} ListNode;

ListNode *reverseKGroup(ListNode *head, int k) {
    if (k > 1) {                     // no need to test for `head != NULL`
        int counter = 0;
        ListNode **start = &head;    // place where to store the head of the reversed fragment
        ListNode *currentPtr = head; // pointer to the first node of the fragment
        ListNode *fastPtr = head;    // pointer to the node after the end of the fragment

        while (fastPtr) {
            fastPtr = fastPtr->next;
            counter++;
            if (counter == k) {
                // k nodes between CurrentPtr and fastPtr: reverse the fragment
                ListNode *lastPtr = currentPtr;
                ListNode *prevPtr = fastPtr;
                while (counter) {
                    ListNode *nextPtr = currentPtr->next;
                    currentPtr->next = prevPtr;
                    prevPtr = currentPtr;
                    currentPtr = nextPtr;
                    counter--;
                }
                *start = prevPtr;
                start = &lastPtr->next;
            }
        }
    }
    return head;
}

void printList(const char *prefix, const ListNode *p, const char *suffix) {
    while (p) {
        printf("%s%d", prefix, p->data);
        prefix = ", ";
        p = p->next;
    }
    printf("%s", suffix);
}

ListNode *test(ListNode *list, int k) {
    printf("reverseKGroup(%d): ", k);
    list = reverseKGroup(list, k);
    printList("", list, "\n");
    return reverseKGroup(list, k); // undo k-reversal
}

int main() {
    ListNode a[10], *list = a;
    for (int i = 0; i < 10; i++) {
        a[i].next = i + 1 < 10 ? &a[i + 1] : NULL;
        a[i].data = i + 1;
    }
    for (int k = 0; k <= 11; k++) {
        list = test(list, k);
    }
    return 0;
}

Output:

reverseKGroup(0): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverseKGroup(1): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverseKGroup(2): 2, 1, 4, 3, 6, 5, 8, 7, 10, 9
reverseKGroup(3): 3, 2, 1, 6, 5, 4, 9, 8, 7, 10
reverseKGroup(4): 4, 3, 2, 1, 8, 7, 6, 5, 9, 10
reverseKGroup(5): 5, 4, 3, 2, 1, 10, 9, 8, 7, 6
reverseKGroup(6): 6, 5, 4, 3, 2, 1, 7, 8, 9, 10
reverseKGroup(7): 7, 6, 5, 4, 3, 2, 1, 8, 9, 10
reverseKGroup(8): 8, 7, 6, 5, 4, 3, 2, 1, 9, 10
reverseKGroup(9): 9, 8, 7, 6, 5, 4, 3, 2, 1, 10
reverseKGroup(10): 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
reverseKGroup(11): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10