725. Split Linked List in Parts

Description

The problem involves splitting a singly-linked list into k parts. Each part should be as equal in size as possible, and any excess nodes should be added to the first few parts. The goal is to return an array where each element represents the head of one of these parts.

Intuition

To solve this problem, we need to determine how many nodes each part should have. First, by counting the total number of nodes in the list, we can decide the base size of each part and distribute any remaining nodes to the first few parts. This ensures that the parts are as balanced as possible in terms of size.

Approach

1. Counting the Nodes: We start by counting the total number of nodes in the linked list.
2. Calculate Part Sizes: If the number of nodes count is less than or equal to k, each node will form its own part, with the remaining parts being null. If count is greater than k, each part will get at least count // k nodes. The first count % k parts will receive one extra node.
3. Splitting the List: Traverse the list again, and for each part, we traverse the number of nodes assigned to that part. After completing the traversal for a part, we sever the list and move to the next part.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the linked list. We traverse the list twice—once to count the nodes and once to split the list.

Space Complexity:

O(k), where k is the number of parts. We need additional space to store the resulting parts array.

Code

C++

class Solution {
public:
    vector splitListToParts(ListNode* head, int k) {
        vector arr(k, nullptr);
        if (k == 1) {
            arr[0] = head;
            return arr;
        }

        // Count the total number of nodes
        int count = 0;
        ListNode* current = head;
        while (current != nullptr) {
            count++;
            current = current->next;
        }

        if (count <= k) {
            current = head;
            for (int i = 0; i < count; i++) {
                arr[i] = head;
                ListNode* tail = head;
                head = head->next;
                tail->next = nullptr;
            }
            return arr;
        }

        int extraCount = count % k;
        int elementsCount = count / k;

        for (int i = 0; i < k; i++) {
            arr[i] = head;
            int currentPartSize = elementsCount + (extraCount > 0 ? 1 : 0);
            extraCount--;

            for (int j = 0; j < currentPartSize - 1; j++) {
                head = head->next;
            }

            if (head != nullptr) {
                ListNode* tail = head;
                head = head->next;
                tail->next = nullptr;
            }
        }

        return arr;
    }
};

Python

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

class Solution:
    def splitListToParts(self, head: ListNode, k: int):
        # If k is 1, return the head
        if k == 1:
            return [head]
        
        # Count the total number of nodes
        count = 0
        current = head
        while current:
            count += 1
            current = current.next
        
        arr = [None] * k

        if count <= k:
            for i in range(count):
                arr[i] = head
                tail = head
                head = head.next
                tail.next = None
            return arr
        
        extraCount = count % k
        elementsCount = count // k

        for i in range(k):
            arr[i] = head
            currentPartSize = elementsCount + (1 if extraCount > 0 else 0)
            extraCount -= 1

            for j in range(currentPartSize - 1):
                head = head.next

            if head:
                tail = head
                head = head.next
                tail.next = None

        return arr

Java

public class Solution {

    public ListNode[] splitListToParts(ListNode head, int k) {
        if (k == 1) {
            return new ListNode[] { head };
        }
        int count = 0;
        ListNode current = head, tail;
        ListNode[] arr = new ListNode[k];

        // Count the total number of nodes
        while (current != null) {
            count++;
            current = current.next;
        }

        if (count <= k) {
            for (int i = 0; i < count; i++) {
                arr[i] = head;
                tail = head;
                head = head.next;
                tail.next = null;
            }
            for (int i = count; i < k; i++) {
                arr[i] = null;
            }
            return arr;
        }

        int extraCount = count % k, elementsCount = count / k;
        for (int i = 0; i < k; i++) {
            arr[i] = head;
            int currentPartSize = elementsCount + (extraCount > 0 ? 1 : 0);
            extraCount--;
            for (int j = 0; j < currentPartSize - 1; j++) {
                head = head.next;
            }
            tail = head;
            head = head.next;
            tail.next = null;
        }
        return arr;
    }
}

JavaScript

var splitListToParts = function(head, k) {
    if(k==1) {
        return [head]
    }
    let count = 0, current = head, tail, arr = []
    while(current) {
        count++
        current = current.next
    }
    if(count <= k) {
        for(let i=0; i0) {
            tail = head
            head = head.next
            extraCount--
        }
        tail.next = null
    }
    return arr
};