Identifying the split pattern
The linked list split technique can only be applied to some specific problems. These are generally easy or medium problems in which we must split a linked list into one or smaller lists. However, there may be some problems where we need to split a list that may have a more straightforward solution than applying the split technique. For example, we can split a list in half using the fast and slow pointer technique, and the split list technique may be overkill. If the problem statement or its solution follows the generic template below, it can be solved by applying the split list technique.
k lists.Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the split technique.
Problem statement: Given a singly linked list and an integer `k` split the list into `k` lists such that their concatenation results in the original lists. The length of all parts should be equal. If that is not possible, the difference between the size of any two lists should not be greater than one, and the list occurring earlier should have a greater size.
Split the given list into k lists
Split technique solution
We need to split a given list into k parts, and this fits the generic template from the split pattern we learned earlier.
k lists.We first find the length of the given list and divide it by k to calculate the minimum number of nodes each of the k split lists will have. We save this value in a variable partSize. The length may not be multiple of k, which means that some split lists will have partSize + 1 nodes. We create a variable bigLists and initialize it with length % k, which is the number of lists that will have partSize + 1 nodes in them.
Find length, size of each sublist and the number of big lists
We then apply the split list technique by creating two arrays of ListNode references dummy and tails of size k each and initialize all items in them with the references of newly created dummy nodes. We initialize current with head and use it to traverse the list from start to end. We also initialize two variables idx and count with 0 to to keep track of the current split list and the number of nodes already added to it. We then iterate the list and use the variables bigLists and count to update idx when we have added all nodes to the current split list.
Create dummy nodes, tail references and control variables
In each iteration, we add the node held in current at the end of the split list denoted by idx and increment count. If we have any bigLists left i.e. bigLists > 0 it means the current split list (denoted by idx) should have partSize + 1 nodes, otherwise it should only have partSize nodes.
We check for these conditions to correctly update idx for the subsequent iterations. If bigLists > 0 we check if we have already added partSize + 1 nodes to the current split list be checking if count == partSize + 1 and reset count to 0, decrement bigLists and increment idx. Otherwise, if bigLists == 0 we check if count == partSize reset count to 0 and increment idx. This ensures that we move to the next split list after we have added all nodes to the current split list.
Split the given list into k lists
The implementation of the split list solution is given as follows.
C++
Java
Typescript
Javascript
Python
The above implementation uses the template code of the split list technique to split the list into k lists in a single pass.
Example problems
Most problems that fall under this category are medium problems; a list of a few is given below.
We will now solve these problems to understand the split list technique better.