Задача: 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 {
    var val: Int
    var next: ListNode?
    init(_ val: Int, _ next: ListNode? = nil) {
        self.val = val
        self.next = next
    }
}

func splitListToParts(_ head: ListNode?, _ k: Int) -> [ListNode?] {
    var length = 0
    var node = head
    while node != nil {
        length += 1
        node = node?.next
    }

    let partLength = length / k
    let extraParts = length % k

    var parts: [ListNode?] = []
    node = head
    for i in 0..<k {
        let partHead = node
        let partSize = partLength + (i < extraParts ? 1 : 0)
        for _ in 0..<partSize - 1 {
            node = node?.next
        }
        let nextPart = node?.next
        node?.next = nil
        node = nextPart
        parts.append(partHead)
    }

    return parts
}

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