Understanding the reorder pattern

Some linked list problems require us to reorder the nodes of the given list in place based on some conditions. In most cases, this requires first splitting the list based on the outcome of some function f1 and then merging back the split list together either by using another function f2 or simply concatenating them. These are generally medium difficulty problems that require either the split or merge technique we learned earlier or both. Many such problems may also require using other techniques, such as the reversal or fast and slow pointer technique.

Reordering technique

Consider that we are given a singly linked list whose nodes must be reordered. The problem almost always has a split function f1 that we use to split the list into multiple lists using the split technique.

Consider the example execution below, where we use the function f1 to split the list into two lists such that nodes with even indices go to one list and those with odd indices go to the other list.

In most cases, concatenating these split lists to merge them is sufficient, but sometimes, we may also have a function f2 that must be used to merge the lists. We use the merge technique to merge them back together to solve the problem.

Consider the example execution below, where we use the function f2 that merges alternate nodes to merge back the split lists starting with the second list, effectively reordering the nodes.

The reordering technique is simply a combination of the split and merge techniques used in tandem to reorder nodes in the given list.

Algorithm

The algorithm given below summarizes the reorder technique for two lists. It can be easily extended for k lists.

Algorithm

• Step 1: Use the split technique to split the list in two using the function `f1`
• Step 2: Use the merge technique to merge the two lists using the function `f2`.
• Step 3: Return the head of the merged list.

Implementation

Given below is the generic code implementation to split a list in two using the function f1 and then merging them using the function f2.

Complexity Analysis

The runtime and space complexity for the reorder technique that splits the list into two lists is pretty easy to understand. We traverse the entire list to split it that has a linear O(N) runtime complexity. If we only need to concatenate the split lists to merge them, it takes constant O(1) time; otherwise, we may need to traverse both split lists completely in the worst case, which has a linear, total O(N) runtime complexity. We traverse the entire list to split it in any case, and so the runtime complexity in any case is O(N).

When we reorder a list by splitting it into two, we only create two dummy nodes and update references, so the space complexity is constant, O(1), in any case.

Best Case:

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case:

• Space Complexity - O(1)
• Time Complexity - O(N)