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

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

Пример:

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

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

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

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

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

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function splitListToParts($root, $k) {
    $length = 0;
    $node = $root;
    while ($node != null) {
        $length++;
        $node = $node->next;
    }

    $partLength = intdiv($length, $k);
    $extraParts = $length % $k;

    $parts = array_fill(0, $k, null);
    $node = $root;
    for ($i = 0; $i < $k; $i++) {
        $partHead = $node;
        $partSize = $partLength + ($i < $extraParts ? 1 : 0);
        for ($j = 0; $j < $partSize - 1; $j++) {
            if ($node != null) {
                $node = $node->next;
            }
        }
        if ($node != null) {
            $nextPart = $node->next;
            $node->next = null;
            $node = $nextPart;
        }
        $parts[$i] = $partHead;
    }

    return $parts;
}

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