Reverse a Linked List in k-groups Editorial

Practice Problem Link: Reverse a Linked List in k-groups

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list and a positive number k, reverse the nodes in groups of k.

All the remaining nodes after multiples of k should be left as it is.

Approach

The idea is to reverse each sub-list of length k recursively. 

• Traverse the list till a sub-list of length k is found. 
• If the length of a sub-list is less than k then simply return the head of the sublist.
• Otherwise, reverse this sub-list and recursively call the reverse function for the rest of the list 
• Link the two sub-lists together and return its head.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n/k)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* reverseLinkedListKGroup(ListNode* head, int k) {
	ListNode* currentNode = head;
	int totalNodes = 0;
	while (currentNode != NULL && totalNodes < k) {
		currentNode = currentNode->next;
		totalNodes++;
	}
	if (totalNodes < k) {
		return head;
	}
	currentNode = head;
	ListNode* prevNode = NULL;
	ListNode* nextNode;
	int nodeCount = 0;
	while (nodeCount < k) {
		nextNode = currentNode->next;
		currentNode->next = prevNode;
		prevNode = currentNode;
		currentNode = nextNode;
		nodeCount++;
	}
	head->next = reverseLinkedListKGroup(nextNode, k);
	return prevNode;	
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode reverseLinkedListKGroup(ListNode head, int k) {
		ListNode currentNode = head;
		int totalNodes = 0;
		while (currentNode != null && totalNodes < k) {
			currentNode = currentNode.next;
			totalNodes++;
		}
		if (totalNodes < k) {
			return head;
		}
		currentNode = head;
		ListNode prevNode = null;
		ListNode nextNode = null;
		int nodeCount = 0;
		while (nodeCount < k) {
			nextNode = currentNode.next;
			currentNode.next = prevNode;
			prevNode = currentNode;
			currentNode = nextNode;
			nodeCount++;
		}
		head.next = reverseLinkedListKGroup(nextNode, k);
		return prevNode;
	}
}