Understanding the split pattern

Many linked list problems require splitting a given linked list into two or more lists based on the outcome of some function. One solution to this problem is traversing the list for every new list that has to be created and copying items from the original list into the new nodes created for the new lists. However, this requires multiple passes over the list and is inefficient. Also, in many cases, we need to split the original list into separate lists instead of creating copies of nodes. The linked list split technique can be applied to such problems to solve them efficiently in a single pass.

Linked list split technique

Consider we are given a singly linked list that we need to split into k lists using a function f that maps every node in the original list to the list it should go to after splitting. the functionfsimply round robins amongst all theklists. The split technique uses dummy nodes to simplify splitting the original lists. We create two arrays of node references dummy and tails of size k each. Both the arrays initialized it with references of newly created dummy nodes where the item at the index i is the dummy node for the list i.

Consider the example below, where k = 3.

We initialize a current reference with the head of the list and traverse the original list from start to end. In each iteration, we use the function f to identify which list the current node should go to. We get the tail node for that list from the tail array, update its next section to hold the current node, and update the tail reference. Then, we move current one step ahead for the next iteration and finally set the next section of the new tail node to null. This process is repeated until we reach the end of the list when the original list is split into k lists.

At the end of all iterations, we iterate in dummy and move the references one step ahead to hold the real head of the corresponding list and delete the dummy node.

Algorithm

The algorithm given below summarizes the linked list split technique to split a list into k lists.

Algorithm

• Step 1: Create two arrays of node references `dummy` and `tails` of size `k` and initialize each item in both arrays with the reference of a newly created dummy node.
• Step 2: Create a reference `current` and initialize it with the head of the list.
• Step 3: Loop while `current` != `null` and do the following:
  • Step 3.1: Apply the function `f` to the `current` node and retrieve `idx`, which is the index of the list where this node should be placed.
  • Step 3.2: Add the `current` node to the end of the list stored at `idx` using `tails` array.
  • Step 3.3: Update `tails[idx]` to now store the reference of the new tail node.
  • Step 3.4: Update the `current` pointer to hold the reference of the node after the `current` node.
  • Step 3.5: Set the next section of `tails[idx]` to `null`
• Step 4: Move all the dummy nodes one step ahead to obtain the heads of the split lists and delete the old dummy nodes.

Implementation

Given below is the generic code implementation to split a given linked list into k lists based on the outcome of a function f. 

Complexity Analysis

Looking at the algorithm, the runtime and space complexity are pretty easy to understand. We traverse the given linked list from start to end, so the time complexity is linear O(N) in any case.

We create two arrays of size k each to store references to dummy nodes and tail nodes. We also create k dummy nodes to simplify the implementation, so the space complexity is O(K) in any case.

Best Case: K = 1

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

Worst Case: K = N

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