Identifying the merge pattern

The linked list merge technique can only be applied to some specific problems. These are generally easy or medium problems where we merge multiple lists into a single list based on the outcome of some function f.  Sometimes, there may be more than one way to solve such problems; however, using the merge technique often has the cleanest and most straightforward solution. If the problem statement or its solution follows the generic template below, it can be solved by applying the merge technique.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the merge technique.

Problem statement: Given two singly linked lists, merge them by splicing alternate nodes from both lists together. The merged list should start with the first node of the first list.

Merge technique solution

We need to merge two lists to create a merged list; this fits the generic template from the merge pattern we learned earlier.

We use the merge technique by creating a dummy node and tail reference for the merged list and iterating both lists using two references currentA and currentB. We also create a boolean variable mergeFirst to decide if the node from the first list should be added to the merged list and initialize it to true. In each iteration, we flip the value of mergeFirst to choose a node from the other list in subsequent iterations.

At the end of all iterations we check if either of the lists is not completely traversed and attach any remaining nodes to the end of the merged list. Finally, we delete the dummy node and return the real head of the merged list.

The implementation of the merge list solution is given as follows.

The above implementation uses the template code of the merge technique to merge two lists into a single list in a single pass.

Example problems

Most problems that fall under this category are easy or medium problems where we need to merge two lists. Most of the time, it is easy to identify problems that can be solved using the merge technique. A list of a few such problems is given below.

• Alternate node fusion
• Merge sorted lists
• Merge sorted lists II
• List addition

We will now solve these problems to understand the merge technique better.