Reversing a linked list in groups of given size

Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k.

For example consider the following diagram of input and output linked lists for k = 3.

There are no tricks involved in the solution for this problem. It is just an implementation challenge where we have to carefully manipulate pointers to achieve the desired result.

Here is the strategy. The first step is to subdivide the list into chunks of size k. The last chunk maybe less than size k (depends on whether the length of the linked list is a multiple of k).

Keep a reference to the beginning of the sub-list, and traverse through k nodes.

Reverse the sub-list and re-arrange the begin and end pointers for the reversed sub-list.

The following diagram might give an overview of the process.

Here is the C++ implementation including recursive as well as iterative implementation.

We can consider the following test cases to test the program.

An empty/NULL list
List with just one node
List with multiple of k size
List with non-multiple of k size
Arbitrary list with k = 0, k= 1, k= length(list)
Any combination of the above.

	#include <iostream>

	using namespace std;

	struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	};

	ListNode * Add(ListNode *head, int d)
	{
	ListNode *temp = new ListNode(d);
	temp->next = head;
	return temp;
	}

	void Print(ListNode *head)
	{
	if( !head )
	{
	cout << "Empty" << endl;
	return;
	}
	while( head )
	{
	cout << head->val << " ";
	head = head->next;
	}
	cout << endl;
	}

	//Helper method reverse a list
	ListNode * ReverseList(ListNode *head)
	{
	if( !head \|\| !head->next )
	return head;
	ListNode curPtr = head, prevPtr = NULL;

	while( curPtr != NULL )
	{
	ListNode * nextPtr = curPtr->next;
	curPtr->next = prevPtr;
	prevPtr = curPtr;
	curPtr = nextPtr;
	}
	return prevPtr;
	}
	//Recursive method
	ListNode ReverseSublist(ListNode head, int k)
	{
	//Boundary case; list/sublist size is empty
	if( !head \|\| !head->next \|\| k < 2 )
	{
	return head;
	}
	int i;
	ListNode current = head, begin = head, *prev = NULL;
	//Form a sublist of size k
	for( i = 0; current!= NULL && i < k; i++ )
	{
	prev = current;
	current = current->next;
	}
	prev->next = NULL;
	ListNode* revSublist = ReverseList(begin);
	begin->next = ReverseSublist(current,k);
	return revSublist;
	}
	//Iterative method
	/ListNode ReverseSublist(ListNode *head, int k)
	{
	//Boundary case; list/sublist size is empty
	if( !head \|\| !head->next \|\| k < 2 )
	{
	return head;
	}
	ListNode newHead = NULL, prevListEnd = NULL;
	ListNode *current = head;
	int i;
	while( current != NULL )
	{
	ListNode p = current, prev = NULL;
	//Form a sublist of size k
	for( i = 0; p!= NULL && i < k; i++ )
	{
	prev = p;
	p = p->next;
	}
	prev->next = NULL;
	ListNode* revSublist = ReverseList(current);
	if( !newHead ) //update newHead if this is first sublist
	{
	newHead = revSublist;
	}
	else
	{
	prevListEnd->next = revSublist;
	}
	prevListEnd = current;
	current->next = p;
	current = p;
	}
	return newHead;
	}
	*/
	ListNode *BuildList()
	{
	ListNode *head = NULL;
	head = Add(head,6);
	head = Add(head,5);
	head = Add(head,4);
	head = Add(head,3);
	head = Add(head,2);
	head = Add(head,1);
	return head;
	}

	void Test1()
	{
	ListNode *list = BuildList();
	list = ReverseSublist(list,2);
	Print(list);
	}
	void Test2()
	{
	ListNode *list = BuildList();
	list = ReverseSublist(list,3);
	Print(list);
	}
	void Test3()
	{
	ListNode *list = BuildList();
	list = ReverseSublist(list,6);
	Print(list);
	}
	void Test4()
	{
	ListNode *list = BuildList();
	list = ReverseSublist(list,1);
	Print(list);
	}
	void Test5()
	{
	ListNode *list = BuildList();
	list = ReverseSublist(list,4);
	Print(list);
	}
	void Test()
	{
	Test1();
	Test2();
	Test3();
	Test4();
	Test5();
	}
	int main()
	{
	Test();
	return 0;
	}

view raw ReverseSublist.cpp hosted with

by GitHub

Leave a Reply Cancel reply