Задача: 725. Split Linked List in Parts
Сложность: medium

Учитывая голову односвязного списка и целое число k, разбейте связный список на k последовательных частей связного списка. Длина каждой части должна быть как можно более одинаковой: никакие две части не должны иметь размер, отличающийся более чем на единицу. Это может привести к тому, что некоторые части будут нулевыми. Части должны располагаться в порядке появления во входном списке, и части, появившиеся раньше, всегда должны иметь размер, больший или равный частям, появившимся позже. Возвращается массив из k частей.

Пример:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

👨‍💻 Алгоритм:

1⃣Определите общую длину связного списка.

2⃣Вычислите базовый размер каждой части и количество частей, которые должны быть на одну единицу длиннее.

3⃣Разделите список на части, присваивая каждую часть в массив результатов.

😎 Решение:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int length = 0;
        ListNode node = root;
        while (node != null) {
            length++;
            node = node.next;
        }

        int partLength = length / k;
        int extraParts = length % k;

        ListNode[] parts = new ListNode[k];
        node = root;
        for (int i = 0; i < k; i++) {
            ListNode partHead = node;
            int partSize = partLength + (i < extraParts ? 1 : 0);
            for (int j = 0; j < partSize - 1; j++) {
                if (node != null) node = node.next;
            }
            if (node != null) {
                ListNode nextPart = node.next;
                node.next = null;
                node = nextPart;
            }
            parts[i] = partHead;
        }

        return parts;
    }
}

Ставь 👍 и забирай 📚 Базу знаний