Jobs

Interviews

Discussions

Split Linked List in Parts

Medium

Google

3 views

Topics:

Linked Lists

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Constraints:

The number of nodes in the list is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Split Linked List in Parts

Medium

Google

3 views

Topics:

Linked Lists

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Constraints:

The number of nodes in the list is in the range [0, 1000].
0 <= Node.val <= 1000
1 <= k <= 50

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'k'? Can 'k' be zero, negative, or larger than the length of the linked list?
If the length of the linked list is not divisible by 'k', how should the extra nodes be distributed among the parts? Should the earlier parts always receive the extra nodes?
What should be returned if the input linked list is empty (head is null)? Should I return an array of 'k' nulls, an empty array, or something else?
Are the values within the linked list nodes themselves relevant to the problem, or am I only concerned with the structure and length of the list?
Can I modify the original linked list, or do I need to create new linked lists for each part?

Brute Force Solution

Approach

The brute force method for splitting a linked list involves exploring every possible way to divide the list into the desired number of parts. We essentially try out every combination of split points to see what works. It is a try-it-and-see strategy.

Here's how the algorithm would work step-by-step:

First, figure out the basic size of each part by dividing the total number of items in the linked list by the number of parts you want.
Start by creating the first part. Try putting just the first item in the first part, then the first two items, then the first three items, and so on.
For each potential first part, check if it's a valid part according to the size we calculated earlier.
If it's valid, then move on to the second part and repeat the process: try making different size parts until you find a valid one, always making sure we have enough list items left for the remaining parts.
Keep going until you've created all the parts.
Store each valid way you find to split the list into the required number of parts.
After trying absolutely every possible way to divide the list, compare all the valid splits you saved, then choose the 'best' one based on how evenly the items are distributed amongst the parts.

Code Implementation

def split_linked_list_in_parts_brute_force(head, k):
    nodes_in_linked_list = 0
    current_node = head
    while current_node:
        nodes_in_linked_list += 1
        current_node = current_node.next_node

    base_part_size = nodes_in_linked_list // k
    extra_nodes = nodes_in_linked_list % k
    all_possible_splits = []

    def generate_splits(remaining_nodes, parts_remaining, current_split, current_node):
        if parts_remaining == 0:
            if remaining_nodes == 0:
                all_possible_splits.append(current_split.copy())
            return

        # We iterate through possible part sizes
        for part_size in range(1, remaining_nodes + 1):
            part_head = current_node
            part_tail = current_node
            for _ in range(part_size - 1):
                if part_tail:
                    part_tail = part_tail.next_node
            
            if part_tail:
                next_node = part_tail.next_node
                part_tail.next_node = None # Terminate the part
            else:
                next_node = None
                
            expected_part_size = base_part_size + (1 if parts_remaining <= extra_nodes else 0)

            # Valid splits must be close to the ideal size
            if abs(part_size - expected_part_size) <= (1 if base_part_size > 0 else 1):
                current_split.append(part_head)
                generate_splits(remaining_nodes - part_size, parts_remaining - 1, current_split, next_node)
                current_split.pop() #Backtrack

    generate_splits(nodes_in_linked_list, k, [], head)

    #If the base part size is zero, it is always preferrable
    if base_part_size == 0:
        return all_possible_splits[0] if all_possible_splits else [None] * k
    
    best_split = None
    min_variance = float('inf')

    # Iterate through the possible splits
    for possible_split in all_possible_splits:
        part_sizes = [0 if part is None else self.linked_list_length(part) for part in possible_split]
        average_part_size = sum(part_sizes) / k
        variance = sum([(size - average_part_size) ** 2 for size in part_sizes]) / k

        #Find split with minimum variance
        if variance < min_variance:
            min_variance = variance
            best_split = possible_split

    return best_split if best_split else [None] * k

    def linked_list_length(self, head):
        length = 0
        current = head
        while current:
            length += 1
            current = current.next_node

Big(O) Analysis

Time Complexity

O(n^p) – The algorithm explores every possible way to divide the linked list of n nodes into p parts. In the worst-case scenario, for each possible split point, we iterate through the list to create and validate the parts. Since we are trying all possible combinations of split points to form 'p' parts from 'n' elements, the number of combinations grows exponentially. Therefore, the time complexity is O(n^p), where 'n' is the number of nodes and 'p' is the number of parts. The precise complexity is difficult to express as a polynomial but is driven by the nested iterations required to evaluate all possible partitionings.

Space Complexity

O(N^K) – The algorithm stores each valid way to split the list into K parts. In the worst case, it explores a large portion of possible splits. Each valid split requires storing references to the head nodes of each of the K parts, potentially requiring space proportional to K * number of valid splits. The number of valid splits grows exponentially with N (the number of nodes in the linked list) and K (the number of parts). Therefore, in the worst-case scenario, the space complexity is O(N^K) due to storing all possible valid splits.

Optimal Solution

Approach

The goal is to divide a linked list into a specific number of parts, distributing the nodes as evenly as possible. We first determine the base size of each part and the number of parts that might have one extra node. Then we simply create the parts by iterating through the original list.

Here's how the algorithm would work step-by-step:

First, figure out how many total nodes are in the list.
Determine the minimum number of nodes each part should have by dividing the total number of nodes by the desired number of parts. This is the base size.
Calculate how many of the parts will have one extra node. This is the remainder of the division from the previous step.
Create an empty collection of lists to hold the resulting parts.
Start iterating through the original linked list.
For each part, determine its size: either the base size or the base size plus one, depending on whether this part should get an extra node.
Extract the appropriate number of nodes from the original linked list to form this part.
Add the newly created part to the collection of parts.
Repeat the process until the desired number of parts is reached or the original list is empty.
Return the collection of list parts.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def split_linked_list_in_parts(head, number_of_parts):
    list_length = 0
    current_node = head
    while current_node:
        list_length += 1
        current_node = current_node.next

    base_size = list_length // number_of_parts
    number_of_larger_parts = list_length % number_of_parts

    result = []
    current_node = head

    for i in range(number_of_parts):
        # Determine the size of the current part.
        part_size = base_size + (1 if i < number_of_larger_parts else 0)
        
        # Initialize the head of the current part.
        part_head = current_node
        
        # Traverse the list to create the current part.
        for j in range(part_size - 1):
            if current_node:
                current_node = current_node.next
        
        # Break the link to the next part.
        if current_node:
            next_node = current_node.next
            current_node.next = None

        # Add the part to the result
            current_node = next_node
        result.append(part_head)

    # Pad the result with None if needed.
    while len(result) < number_of_parts:
        result.append(None)
    
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once to determine the total number of nodes, which takes O(n) time, where n is the number of nodes in the linked list. It then iterates again to split the list into parts. This second iteration also visits each node once to form the sublists. Therefore, the overall time complexity is dominated by these two linear passes through the linked list, resulting in O(n) time complexity.

Space Complexity

O(k) – The auxiliary space complexity is dominated by the creation of a collection (e.g., an array or list) to store the resulting k linked list parts. The plain English steps describe adding each created part to this collection. Therefore, the space required grows linearly with the number of parts, k, regardless of the input list size, N. The additional variables used during the linked list splitting process take constant space and do not depend on k or N.

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return an array of k nulls, as there are no nodes to distribute.
k is 1 (split into one part)	Return an array containing only the original linked list.
k is greater than the length of the linked list	The first 'length of list' elements of the returned array contain single-node lists, the remaining k - 'length of list' elements are null.
k is equal to the length of the linked list	Return an array where each element is a list containing a single node from the original list.
Linked list with only one node	The first element of the returned array contains the single-node list, the remaining k-1 elements are null.
Large linked list (performance)	Iterative approach avoids stack overflow issues for large linked lists and provides O(N) time complexity for traversal.
k is zero or negative	Throw an IllegalArgumentException as it's impossible to split into zero or negative parts.
Very long linked list with very small k	The algorithm should distribute the extra nodes evenly among the first few parts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for 'k'? Can 'k' be zero, negative, or larger than the length of the linked list?
If the length of the linked list is not divisible by 'k', how should the extra nodes be distributed among the parts? Should the earlier parts always receive the extra nodes?
What should be returned if the input linked list is empty (head is null)? Should I return an array of 'k' nulls, an empty array, or something else?
Are the values within the linked list nodes themselves relevant to the problem, or am I only concerned with the structure and length of the list?
Can I modify the original linked list, or do I need to create new linked lists for each part?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out the basic size of each part by dividing the total number of items in the linked list by the number of parts you want.
Start by creating the first part. Try putting just the first item in the first part, then the first two items, then the first three items, and so on.
For each potential first part, check if it's a valid part according to the size we calculated earlier.
If it's valid, then move on to the second part and repeat the process: try making different size parts until you find a valid one, always making sure we have enough list items left for the remaining parts.
Keep going until you've created all the parts.
Store each valid way you find to split the list into the required number of parts.
After trying absolutely every possible way to divide the list, compare all the valid splits you saved, then choose the 'best' one based on how evenly the items are distributed amongst the parts.

Code Implementation

def split_linked_list_in_parts_brute_force(head, k):
    nodes_in_linked_list = 0
    current_node = head
    while current_node:
        nodes_in_linked_list += 1
        current_node = current_node.next_node

    base_part_size = nodes_in_linked_list // k
    extra_nodes = nodes_in_linked_list % k
    all_possible_splits = []

    def generate_splits(remaining_nodes, parts_remaining, current_split, current_node):
        if parts_remaining == 0:
            if remaining_nodes == 0:
                all_possible_splits.append(current_split.copy())
            return

        # We iterate through possible part sizes
        for part_size in range(1, remaining_nodes + 1):
            part_head = current_node
            part_tail = current_node
            for _ in range(part_size - 1):
                if part_tail:
                    part_tail = part_tail.next_node
            
            if part_tail:
                next_node = part_tail.next_node
                part_tail.next_node = None # Terminate the part
            else:
                next_node = None
                
            expected_part_size = base_part_size + (1 if parts_remaining <= extra_nodes else 0)

            # Valid splits must be close to the ideal size
            if abs(part_size - expected_part_size) <= (1 if base_part_size > 0 else 1):
                current_split.append(part_head)
                generate_splits(remaining_nodes - part_size, parts_remaining - 1, current_split, next_node)
                current_split.pop() #Backtrack

    generate_splits(nodes_in_linked_list, k, [], head)

    #If the base part size is zero, it is always preferrable
    if base_part_size == 0:
        return all_possible_splits[0] if all_possible_splits else [None] * k
    
    best_split = None
    min_variance = float('inf')

    # Iterate through the possible splits
    for possible_split in all_possible_splits:
        part_sizes = [0 if part is None else self.linked_list_length(part) for part in possible_split]
        average_part_size = sum(part_sizes) / k
        variance = sum([(size - average_part_size) ** 2 for size in part_sizes]) / k

        #Find split with minimum variance
        if variance < min_variance:
            min_variance = variance
            best_split = possible_split

    return best_split if best_split else [None] * k

    def linked_list_length(self, head):
        length = 0
        current = head
        while current:
            length += 1
            current = current.next_node

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out how many total nodes are in the list.
Determine the minimum number of nodes each part should have by dividing the total number of nodes by the desired number of parts. This is the base size.
Calculate how many of the parts will have one extra node. This is the remainder of the division from the previous step.
Create an empty collection of lists to hold the resulting parts.
Start iterating through the original linked list.
For each part, determine its size: either the base size or the base size plus one, depending on whether this part should get an extra node.
Extract the appropriate number of nodes from the original linked list to form this part.
Add the newly created part to the collection of parts.
Repeat the process until the desired number of parts is reached or the original list is empty.
Return the collection of list parts.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def split_linked_list_in_parts(head, number_of_parts):
    list_length = 0
    current_node = head
    while current_node:
        list_length += 1
        current_node = current_node.next

    base_size = list_length // number_of_parts
    number_of_larger_parts = list_length % number_of_parts

    result = []
    current_node = head

    for i in range(number_of_parts):
        # Determine the size of the current part.
        part_size = base_size + (1 if i < number_of_larger_parts else 0)
        
        # Initialize the head of the current part.
        part_head = current_node
        
        # Traverse the list to create the current part.
        for j in range(part_size - 1):
            if current_node:
                current_node = current_node.next
        
        # Break the link to the next part.
        if current_node:
            next_node = current_node.next
            current_node.next = None

        # Add the part to the result
            current_node = next_node
        result.append(part_head)

    # Pad the result with None if needed.
    while len(result) < number_of_parts:
        result.append(None)
    
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return an array of k nulls, as there are no nodes to distribute.
k is 1 (split into one part)	Return an array containing only the original linked list.
k is greater than the length of the linked list	The first 'length of list' elements of the returned array contain single-node lists, the remaining k - 'length of list' elements are null.
k is equal to the length of the linked list	Return an array where each element is a list containing a single node from the original list.
Linked list with only one node	The first element of the returned array contains the single-node list, the remaining k-1 elements are null.
Large linked list (performance)	Iterative approach avoids stack overflow issues for large linked lists and provides O(N) time complexity for traversal.
k is zero or negative	Throw an IllegalArgumentException as it's impossible to split into zero or negative parts.
Very long linked list with very small k	The algorithm should distribute the extra nodes evenly among the first few parts.