ishitajuneja's blog

Data structure is among the most critical concepts asked in coding interview assessments at tech companies. This includes product-based companies like Amazon and Microsoft to service companies like TCS and Accenture.

And within data structure, you’re bound to get the ‘Reverse a Linked List in Groups’ question. How you reverse a linked list is critical to cracking the interview round.

The reason why applicants have a hard time solving this problem is because they don’t know what a linked list is and how to reverse it. Well, that’s what this article is about.

 Here learn how you can reverse a linked list in groups of given sizeeasily in a few steps while learning the different approaches used to reverse the list.

Linked lists are an important concept in data structure. As per their technical definition, linked lists are defined as linear data structures with interconnected nodes. Each node contains the information (data) and the address to the next node.

Think of linked lists as the game of Treasure Hunt. In this popular game, the clue in a current scenario leads to the next clue and so on. Likewise, each node in the linked list leads to the next node. The links between the two nodes are called pointers.

Also, note that there are different types of linked lists. These are:

• Singly linked- Each node is joined to another node a single pointer

• Doubly linked- The nodes are joined to one another double pointers. Thus, you can proceed in both directions, forward and backward

• Circular- Here the last node is linked to the first node in addition to a single pointers

The importance of linked lists in programming is immense. They are often employed for the implementation of queues, stacks, or other abstract data types. Doubly linked and circular linked lists are used for more complex problems in data structure like Fibonacci Heap.

Their efficient insertion and deletion is what makes linked lists so popular among programmers. They are used in many mainstream languages like C, C++, Java, and Python.

Don’t confuse linked lists with arrays, even though both are used for storing the elements. Understanding the difference between the two is crucial to solving the problem.

Arrays are used for storing elements in a contiguous memory location, whereas in linked lists, the elements aren’t held at contiguous memory locations. 

In other words, linked lists are less rigid when it comes to the storage structure. That’s why they contain information to the next node, thereby giving a reference.

So what does reversing a linked list in groups mean?

Since all technical rounds are time-based, many applicants don’t put enough time in understanding the question. This, as hiring managers would tell, is a mistake. You should also read and understand the problem before attempting. You can also look at the reverse level order traversal. 

When you get a “reversing a linked list” type of query, there are two similar questions. These are:

• Reverse a linked list in groups

• Reverse a linked list

The solution to both of these questions is different. One wouldn’t substitute for another. Therefore, it’s really crucial to read and understand the query before attempting.

For the second question, you just have to reverse the linked list. More specifically, you have to reverse the pointers. So for ( 3→2→1), the reverse list would be (1→2→3). You can either follow the iterative or recursive approach.

The point of focus for this article is how to reverse a linked list in groups of given size. So instead of simply reversing the linked list, you need to reverse it in groups. Here’s what the input looks like:

Input: 1->2->3->4->5->6->7->8->NULL (k=3)

K is always a positive integer and here serves as an input to the function. It also defines the size of the group. The output of this would be:

Output: 3->2->1->6->5->4->8->7->NULL

Noticed the difference?

Here, the linked list was reversed in groups of 3. So there are 3 nodes in each group. Nodes 1, 2, 3 are one group, nodes 5, 6, 7 are the next group and so on. The last group (7, 8) is incomplete. So they need to stay the same.

You need to produce the same result when asked to reverse a linked list in groups of given size. Also, you don’t have to change the value of the nodes in the list.

Now let’s see how to solve this problem.

The best approach to reversing a linked list in groups of given size is the following:

• Reverse the first sub-list with size equal to K. You need to keep track of the next and previous node when reversing.

• Define the pointer leading to the next node as ‘next’ and the one pointing to the previous node as ‘prev’

• Then, you have to recursively call the remaining list. Then link the two sub-lists.

• Finally, return ‘prev’. Here, the nodes defined as prev become the head in the new list.

You can apply this approach to solve this problem. In the end, you should get a reversed linked list in groups of k.

Reversing the linked list in a group of given sizeproblems will help you crack the interview. Yes, there will be other questions as well, but this will create a good first impression. 

For the best chances of clearing the technical round, practise other similar linked list data structure problems. Some of them are:

• Detect loop in a linked list

• Remove duplicates from a sorted linked list

• Reverse level order traversal

• Convert a Binary Tree to Circular Doubly Linked list

• Swap the nth node in the beginning with the nth node in the end in this linked list

You can find more similar questions in online mock tests. Do take them up to boost your chances of success.