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 (for example, a predicate that sends odd indexed nodes to one list and even indexed nodes to the other) and then merging back the split list together either by using another function f2 (for example, a rule that picks nodes alternately from the two lists) 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