logo

Abhishek Jha

HomeProjectsExperienceBlogsAboutContact

Abhishek Jha / April 03, 2022

Problem link for practice

Read the Pre-requisites: section.Pre-requisites:#

Linked list

Reverse a linked list

Read the Problem statement: section.Problem statement:#

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.

Read the Example: section.Example:#

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

Output: [2,1,4,3,5]Problem statement

Read the Steps to solve: section.Steps to solve:#

  • We need to reverse all the groups of k nodes and at last if less than k nodes are left, we do nothing.
  • We can reverse each group using reverse the linked list logic.
  • Solve each group separately one after other using recursion and keep attaching result of each operation to linked list.

Read the Image Explanation: section.Image Explanation:#

Image Explanation
Image Explanation
Image Explanation
solution.cpp
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {


        // if head is null or k = 1, do nothing
        if(!head or k == 1) return head;
        ListNode *oldHead = head, *newHead = NULL, *curr = head;


        // go to kth node of group, that will be newHead after reversal
        for(int i = 0; i < k-1; i++) {
            curr = curr->next;
            // if less than k nodes are left, do nothing
            if(!curr) return head;
        }
        newHead = curr;


        // reversing group of k nodes
        ListNode *prev = NULL, *nxt = NULL;
        curr = head;


        for(int i = 0; i < k; i++) {
            nxt = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nxt;
        }


        // attach result of recursively solving remaining n-k nodes
        // to oldHead and return newHead
        oldHead->next = reverseKGroup(curr, k);


        return newHead;
    }
};

If you want article on any specific DSA, CP or Dev related topics. Then do let me know

Share Blog 🚀