Identifying direct application

The linked list reversal algorithm can only be directly applied to specific problems that fall under the reversal pattern. These are generally easy problems where we must revere the entire list of a part of it to solve. If the problem statement or its solution follows the generic template below, it can be solved by using the linked list reversal algorithm directly.

Example

To better understand the problems that can be solved by directly applying the linked list reversal algorithm, let's consider the following problem and see how we can identify it as a direct application.

Problem statement: Given a singly linked list, reverse it in place

Linked list reversal algorithm

The problem description fits the template for the direct application of the reversal pattern we learned earlier.

The complete reversal of the singly linked list is a special case of the reversal algorithm that we learned earlier. We initialize two references current and previous with head and nullptr respectively and traverse the list from the head using current. In each iteration, we save the reference to the next node in a new reference variable, set the the next section of the node to previous, and update the current and previous for the next iteration. At the end of all iterations, previous will be the head of the reversed list.

The implementation of the reversal algorithm to reverse the entire list is given as follows.

Example Problems

Most problems that fall under this category are easy problems; a list of a few is given below.

• Reverse a list
• Reverse first K nodes
• Reverse last K nodes
• Reverse the given segment

We will now solve these problems to understand the direct application of this pattern better.