Jobs

Interviews

Discussions

Split Linked List in Parts

Medium

Split Linked List in Parts

Medium

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 should I return if k is greater than the length of the linked list?
Can the values in the linked list be negative, zero, or have any other constraints?
Is k guaranteed to be a positive integer?
If the list cannot be split perfectly evenly, how should the 'extra' nodes be distributed amongst the sublists?
Should the order of the parts in the output array match the order of nodes in the original linked list?

Brute Force Solution

Approach

The brute force strategy for splitting a linked list involves considering all possible ways to divide the list into the specified number of parts. We essentially explore every combination, ensuring that no possible arrangement is overlooked. This means we try splitting the list at different points until we find valid combinations.

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

Determine how many parts the linked list needs to be split into.
Start by considering the first possible split: assign the first few elements of the list to the first part.
Then, assign the remaining elements to the remaining parts, trying out different splits for each part.
Keep going, trying all the different possible numbers of elements in the first part, then in the second, and so on, until you've looked at all the possible ways to split the list into the required number of parts.
For each way you find to split the list, check if it's a valid split. A split is valid if it creates the correct number of parts.
Once you've tried all possible splits, choose the split that best meets the requirements. The best split may be based on the most even distribution of elements amongst the parts.

Code Implementation

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

def split_linked_list_brute_force(head, parts):
    nodes = []
    current_node = head

    while current_node:
        nodes.append(current_node)
        current_node = current_node.next

    list_length = len(nodes)
    base_size = list_length // parts
    extra_nodes = list_length % parts
    result = []

    start = 0
    for i in range(parts):
        part_size = base_size + (1 if i < extra_nodes else 0)

        # Handle case when part size is zero, create empty list
        if part_size == 0:
            result.append(None)
            continue

        result.append(nodes[start])
        end = start + part_size - 1

        # Need to sever the list to get the required result
        if end + 1 < list_length:
            nodes[end].next = None

        start += part_size

    return result

Big(O) Analysis

Time Complexity

O(n^k) – The described brute force approach explores all possible ways to split the linked list into k parts. For each element, we consider different lengths for the first part, then recurse on the remaining list to split it into k-1 parts. In the worst-case scenario, where we are trying all combinations, the total operations will be on the order of n multiplied by itself k times, leading to approximately n^k total operations, where n is the number of nodes in the linked list and k is the number of parts to split into. Therefore, the time complexity is O(n^k).

Space Complexity

O(1) – The brute force approach, as described, doesn't employ any significant auxiliary data structures. It primarily involves iterating and considering different split points without persistently storing intermediate split configurations or creating temporary lists to hold the parts. Therefore, the space complexity remains constant, requiring only a few variables to track split positions, independent of the linked list size N.

Optimal Solution

Approach

We need to divide the linked list into a specific number of smaller lists. The key is to figure out the ideal size for each small list and how to handle remainders when the original list can't be divided perfectly.

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

First, count the total number of elements in the original linked list.
Divide the total count by the number of desired parts. This gives you the base size for each of the smaller lists.
Calculate the remainder after the division. This tells you how many of the smaller lists need to be one element larger than the base size.
Create the specified number of new lists.
Populate each new list. The first few lists (based on the remainder) will have the larger size, and the remaining lists will have the base size.
Move through the original list, assigning elements to each new list until all elements are distributed.
If any new list is empty (because the original list was shorter than the desired number of parts), make sure to include it to be returned in the array of lists.

Code Implementation

def split_linked_list(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
    remainder = list_length % number_of_parts

    result_list = [None] * number_of_parts
    current_node = head

    for i in range(number_of_parts):
        # First 'remainder' lists are larger
        list_size = base_size + (1 if i < remainder else 0)
        
        if list_size > 0:
            result_list[i] = current_node
            tail = current_node

            for _ in range(list_size - 1):
                tail = tail.next

            next_node = tail.next
            tail.next = None # Terminate current sublist
            current_node = next_node # Move to next sublist's head

    return result_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm first traverses the linked list once to count the total number of nodes, which takes O(n) time where n is the number of nodes. Then, it iterates through the linked list again to split it into k parts. This second traversal also takes O(n) time. The operations of calculating sizes and remainders take constant time O(1). Therefore, the overall time complexity is dominated by the two linear traversals, resulting in O(n) + O(n) which simplifies to O(n).

Space Complexity

O(k) – The algorithm creates an array of size k to store the resulting linked lists. No other significant auxiliary space is used. The space required to store the individual lists themselves is proportional to k, where k is the number of parts to split the linked list into. Therefore, the space complexity is O(k).

Edge Cases

Case	How to Handle
Empty linked list (head is null)	Return an array of k nulls indicating empty sublists.
k is 1 (split into one part)	Return an array containing just the original linked list.
k is greater than the length of the linked list	The first length % k parts will have (length / k) + 1 nodes, and remaining parts will be null.
Length of linked list is much larger than k	Iterate through the list distributing nodes as evenly as possible among the k parts.
Linked list contains duplicate values	The algorithm is not affected by duplicate values; it focuses on splitting the list based on length.
k is zero or negative	Throw an exception or return null since splitting into zero or negative parts is undefined.
Integer overflow calculating length of linked list	Use a long data type or check for overflow before length exceeds the integer max value.
Memory constraints when allocating k linked lists	Allocate the array of size k, but only create the linked list nodes as needed to avoid excessive memory usage.

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 should I return if k is greater than the length of the linked list?
Can the values in the linked list be negative, zero, or have any other constraints?
Is k guaranteed to be a positive integer?
If the list cannot be split perfectly evenly, how should the 'extra' nodes be distributed amongst the sublists?
Should the order of the parts in the output array match the order of nodes in the original linked list?

Brute Force Solution

Approach

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

Determine how many parts the linked list needs to be split into.
Start by considering the first possible split: assign the first few elements of the list to the first part.
Then, assign the remaining elements to the remaining parts, trying out different splits for each part.
Keep going, trying all the different possible numbers of elements in the first part, then in the second, and so on, until you've looked at all the possible ways to split the list into the required number of parts.
For each way you find to split the list, check if it's a valid split. A split is valid if it creates the correct number of parts.
Once you've tried all possible splits, choose the split that best meets the requirements. The best split may be based on the most even distribution of elements amongst the parts.

Code Implementation

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

def split_linked_list_brute_force(head, parts):
    nodes = []
    current_node = head

    while current_node:
        nodes.append(current_node)
        current_node = current_node.next

    list_length = len(nodes)
    base_size = list_length // parts
    extra_nodes = list_length % parts
    result = []

    start = 0
    for i in range(parts):
        part_size = base_size + (1 if i < extra_nodes else 0)

        # Handle case when part size is zero, create empty list
        if part_size == 0:
            result.append(None)
            continue

        result.append(nodes[start])
        end = start + part_size - 1

        # Need to sever the list to get the required result
        if end + 1 < list_length:
            nodes[end].next = None

        start += part_size

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count the total number of elements in the original linked list.
Divide the total count by the number of desired parts. This gives you the base size for each of the smaller lists.
Calculate the remainder after the division. This tells you how many of the smaller lists need to be one element larger than the base size.
Create the specified number of new lists.
Populate each new list. The first few lists (based on the remainder) will have the larger size, and the remaining lists will have the base size.
Move through the original list, assigning elements to each new list until all elements are distributed.
If any new list is empty (because the original list was shorter than the desired number of parts), make sure to include it to be returned in the array of lists.

Code Implementation

def split_linked_list(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
    remainder = list_length % number_of_parts

    result_list = [None] * number_of_parts
    current_node = head

    for i in range(number_of_parts):
        # First 'remainder' lists are larger
        list_size = base_size + (1 if i < remainder else 0)
        
        if list_size > 0:
            result_list[i] = current_node
            tail = current_node

            for _ in range(list_size - 1):
                tail = tail.next

            next_node = tail.next
            tail.next = None # Terminate current sublist
            current_node = next_node # Move to next sublist's head

    return result_list

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 indicating empty sublists.
k is 1 (split into one part)	Return an array containing just the original linked list.
k is greater than the length of the linked list	The first length % k parts will have (length / k) + 1 nodes, and remaining parts will be null.
Length of linked list is much larger than k	Iterate through the list distributing nodes as evenly as possible among the k parts.
Linked list contains duplicate values	The algorithm is not affected by duplicate values; it focuses on splitting the list based on length.
k is zero or negative	Throw an exception or return null since splitting into zero or negative parts is undefined.
Integer overflow calculating length of linked list	Use a long data type or check for overflow before length exceeds the integer max value.
Memory constraints when allocating k linked lists	Allocate the array of size k, but only create the linked list nodes as needed to avoid excessive memory usage.