725. Split Linked List in Parts

leetcode medium

#array#csharp#leetcode#linked-list#medium

Task

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

Пример:

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

Output: [[1],[2],[3],[],[]]

C# solution

matched/original

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    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;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

var splitListToParts = function(head, k) {
    let length = 0;
    let node = head;
    while (node) {
        length += 1;
        node = node.next;
    }

    const partLength = Math.floor(length / k);
    const extraParts = length % k;

    const parts = [];
    node = head;
    for (let i = 0; i < k; i++) {
        let partHead = node;
        let partSize = partLength + (i < extraParts ? 1 : 0);
        for (let j = 0; j < partSize - 1; j++) {
            if (node) node = node.next;
        }
        if (node) {
            let nextPart = node.next;
            node.next = null;
            node = nextPart;
        }
        parts.push(partHead);
    }

    return parts;
};

Python solution

matched/original

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

def splitListToParts(head, k):
    length = 0
    node = head
    while node:
        length += 1
        node = node.next

    part_length = length // k
    extra_parts = length % k

    parts = []
    node = head
    for i in range(k):
        part_head = node
        part_size = part_length + (1 if i < extra_parts else 0)
        for j in range(part_size - 1):
            if node:
                node = node.next
        if node:
            next_part = node.next
            node.next = None
            node = next_part
        parts.append(part_head)

    return parts

Go solution

matched/original

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func splitListToParts(root *ListNode, k int) []*ListNode {
    length := 0
    for node := root; node != nil; node = node.Next {
        length++
    }

    partLength := length / k
    extraParts := length % k

    parts := make([]*ListNode, k)
    node := root
    for i := 0; i < k; i++ {
        partHead := node
        partSize := partLength
        if i < extraParts {
            partSize++
        }
        for j := 0; j < partSize-1; j++ {
            if node != nil {
                node = node.Next
            }
        }
        if node != nil {
            nextPart := node.Next
            node.Next = nil
            node = nextPart
        }
        parts[i] = partHead
    }

    return parts
}

Explanation

Algorithm

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

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

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

😎