Identifying the reorder pattern
The linked list problems that require reordering in place in the list are the only problems that can be solved using the reorder technique. These are generally medium problems where we split the list using some function and then merge them back together using another function. Many such problems also have smaller subproblems that require other techniques like reversal or fast and slow pointers to find the middle. If the problem statement or its solution follows the generic template below, it can be solved by applying the split list technique.
Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the reorder technique.
Problem statement: Given a singly linked list, reorder its nodes so all nodes at even indices come after the nodes at odd indices. The indices start with 1.
Reeorder nodes in the list such that all nodes with even indices come after nodes with odd indices.
Reorder technique solution
We need to reorder the nodes in the given list, and this fits the generic template from the reorder pattern we learned earlier.
To reorder the nodes, we use the split technique to split the given linked list into two such that the first and second split lists have all the nodes with odd and even indices nodes, respectively. We create two dummy nodes dummyA, dummyB and tail references tailA and tailB and initialize them with the respective dummy nodes. We initialize a counter variable index with 0 and iterate the list from start to end using current which is initialized with the head of the list.
In each iteration, we check if the index is odd or even and add the current node to the end of the correct list using one of the tail references. We then increment index and move ahead to repeat the process for the next iteration.
Split the list into two lists
We don't need to use the merge technique to merge the lists, as we can concatenate them in this case. We use the tail and dummy references from the split technique to concatenate them by updating references.
Merge split lists by concatenating them
The implementation of the split list solution is given as follows.
C++
Java
Typescript
Javascript
Python
The above implementation uses the split list technique to split the list into two lists and merge them together by concatenating them.
Example problems
Most problems that fall under this category are medium problems and can be solved by splitting and then contacting the split list. Sometimes, using the merge technique may be required for merging the split using some function, and often, other techniques like reversal or fast and slow pointer techniques may be needed to solve some subproblems. A list of a few problems is given below.
We will now solve these problems to understand the reorder technique better.