Problem of The Day: Split Linked List in Parts

Problem Statement

Intuition

To split the list into k parts, we need to first determine the total length of the linked list. Once the length is known, we can calculate the number of elements that should go into each part. The first remainder parts will contain an extra node to evenly distribute the nodes.

Approach

1. Traverse the linked list to determine its total length.
2. Compute the number of nodes each part should have by dividing the total length by k. Also, determine how many extra nodes should be distributed among the first few parts.
3. Iterate through the list, breaking it into parts of the appropriate sizes, and collect them in the result list.

Complexity

• Time complexity: \(O(n)\) because we traverse the linked list twice: once to find its length and once to split it into parts.

• Space complexity: \(O(k)\) for storing the result in the array of k parts.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        each_list_len = length // k
        remaining = length % k
        list_len = [each_list_len] * k
        for i in range(remaining):
            list_len[i % k] += 1

        curr = head
        res = []
        prev = None
        for i in range(k):
            curr_len = list_len[i]
            res.append(head)
            while curr_len and head:
                curr_len -= 1
                prev = head
                head = head.next

            if prev:
                prev.next = None
        return res

Editorial

Approach 1: Create New Parts

class Solution:
    def splitListToParts(
        self, head: Optional[ListNode], k: int
    ) -> List[Optional[ListNode]]:
        ans = [None] * k

        size = 0
        current = head
        while current is not None:
            size += 1
            current = current.next

        split_size = size // k
        num_remaining_parts = size % k

        current = head
        for i in range(k):
            new_part = ListNode(0)
            tail = new_part

            current_size = split_size
            if num_remaining_parts > 0:
                num_remaining_parts -= 1
                current_size += 1
            for j in range(current_size):
                tail.next = ListNode(current.val)
                tail = tail.next
                current = current.next
            ans[i] = new_part.next

        return ans

• time: O(n)
• space: O(n)

Approach 2: Modify Linked List

class Solution:
    def splitListToParts(
        self, head: Optional[ListNode], k: int
    ) -> List[Optional[ListNode]]:
        ans = [None] * k

        # get total size of linked list
        size = 0
        current = head
        while current is not None:
            size += 1
            current = current.next

        # minimum size for the k parts
        split_size = size // k

        # Remaining nodes after splitting the k parts evenly.
        # These will be distributed to the first (size % k) nodes
        num_remaining_parts = size % k

        current = head
        prev = current
        for i in range(k):
            # create the i-th part
            new_part = current
            # calculate size of i-th part
            current_size = split_size
            if num_remaining_parts > 0:
                num_remaining_parts -= 1
                current_size += 1

            # traverse to end of new part
            j = 0
            while j < current_size:
                prev = current
                if current is not None:
                    current = current.next
                j += 1

            # cut off the rest of linked list
            if prev is not None:
                prev.next = None

            ans[i] = new_part

        return ans

• time: O(n)
• space: O(1)