Understanding the merge pattern

Like splitting a linked list into multiple lists, many linked list problems require merging multiple linked lists into one based on the outcome of some function. Also, in most cases, we must merge the lists by moving around the original nodes instead of creating copies. The linked list merging technique traverses multiple lists simultaneously and merges them in a single pass.

Linked list merging technique

We will learn the merge technique for two lists, but it can be easily extended to merge k lists. Consider that we are given two singly linked lists denoted by headA and headB, and we have to merge them into a single list based on the output of some function f. Given any two nodes, one from each list, the function f decides which node goes before the other node in the merged list.

The merge technique uses a dummy node to simplify the merging algorithm. We create a dummy node and a reference variable tail which we initialize with it. We create two references currentA and currentB and initialize them with headA and headB which we use to traverse the respective lists. We then simultaneously traverse both lists using these references and, in each iteration, apply the function f on nodes held in currentA and currentB to decide which node should be added to the merged list. We use the tail reference to easily add the node at the end of the merged list, update tail, and move ahead either currentA or currentB accordingly.

If either currentA or currentB hits null, it means we have traversed one of the lists completely, and we terminate the iterations. At this point, we identify the list that is not completely traversed and add the remaining nodes at the end of the merged lists to completely merge both lists. Consider the example below where the function f is a simple function that alternates (round robin) between both lists to select the node that goes to the merged list.

Finally, we delete the dummy node and return the reference of the node after it as the real head of the merged list.

Algorithm

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

Algorithm

• Step 1: Create a `dummy` node and initialize a `tail` reference with it.
• Step 2: Create two references `currentA` and `currentB` and initialize them with `headA` and `headB` respectively.
• Step 3: Loop while `currentA` != `null` and `currentB` != `null` and do the following:
  • Step 3.1: Apply the function `f` to the node held in `currentA` and `currentB` to decide which node to add to the merged list.
  • Step 3.2: If `currentA` has to be added, add it to the end of the merged list by updating `tail` and moving `currentA` ahead.
  • Step 3.3: If `currentB` has to be added, add it to the end of the merged list by updating `tail` and moving `currentB` ahead.
  • Step 4: If `currentA` != `null` attach the remaining list to the merged list using `tail`
  • Step 5: If `currentB` != `null` attach the remaining list to the merged list using `tail`
  • Step 6: Delete the `dummy` node and return the next node as real head of merged list.

Implementation

Given below is the generic code implementation to merge two lists into a single list based on the outcome of a function f.

Complexity Analysis

The runtime and space complexity for merging two lists are pretty easy to understand. We traverse both lists together until either one is traversed completely. In the worst case, we may have to traverse both lists completely, with a linear runtime complexity of O(N + M), where N and M are the lengths of the two linked lists. In the best case, one list may be empty, and we merge the other by updating references in constant time so the runtime complexity would be constant O(1).

We only create a dummy node and update references to merge the lists, so the space complexity is constant, O(1), in any case.

Best Case: One list is empty

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

Worst Case: Both lists completely traversed

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