。将链表拆分为多个部分

725。将链表拆分为多个部分

难度：中等

主题：链接列表

给定一个单链表的头和一个整数 k，将链表分割成 k 个连续的链表部分。

每个部分的长度应尽可能相等：任何两个部分的尺寸不应相差超过一倍。这可能会导致某些部分为空。

各部分应按照输入列表中出现的顺序排列，并且较早出现的部分的大小应始终大于或等于较晚出现的部分的大小。

返回由 k 个部分组成的数组。

示例1：

• 输入： head = [1,2,3], k = 5
• 输出： [[1],[2],[3],[],[]]
• 说明：
  • 第一个元素output[0]的output[0].val = 1，output[0].next = null。
  • 最后一个元素output[4]为null，但其作为ListNode的字符串表示形式是[]。

示例2：

• 输入： head = [1,2,3,4,5,6,7,8,9,10], k = 3
• 输出： [[1,2,3,4],[5,6,7],[8,9,10]]
• 说明：
  • 输入已被分割成大小相差最多为 1 的连续部分，并且较早的部分比后面的部分尺寸更大。

约束：

• 列表中的节点数量在 [0, 1000] 范围内。
• 0
• 1

提示：

1. 如果列表中有 N 个节点，以及 k 个部分，则每个部分都有 N/k 个元素，除了前 N%k 部分有一个额外的元素。

解决方案：

关键的观察是每个部分的节点数不应相差超过 1。这意味着：

1. 计算链表的长度。
2. 确定每个部分的最小尺寸（part_size = length // k）。
3. 将额外节点均匀分布在前几个部分（extra_nodes = length % k）。第一个 extra_nodes 部分应各有一个额外节点。

方法

1. 计算长度：遍历链表，求节点总数。
2. 确定各部分的大小：
   • 每个部分应该至少有长度 // k 个节点。
   • 第一个长度 % k 的部分应该有一个额外的节点。
3. 拆分列表：使用循环将链表拆分为 k 部分。对于每个部分：
   • 如果应该有额外的节点，则分配part_size + 1个节点。
   • 如果没有，则分配part_size节点。
4. 空部分：如果列表短于k，则某些部分将为空（null）。

让我们用 PHP 实现这个解决方案：725。将链表拆分为多个部分

<?php
// Definition for singly-linked list.
class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
 /**
 * @param ListNode $head
 * @param Integer $k
 * @return ListNode[]
 */
function splitListToParts($head, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Helper function to create a linked list from an array
function createLinkedList($arr) {
    $head = new ListNode($arr[0]);
    $current = $head;
    for ($i = 1; $i < count($arr); $i++) {
        $current->next = new ListNode($arr[$i]);
        $current = $current->next;
    }
    return $head;
}

// Helper function to print a linked list
function printList($head) {
    $result = [];
    while ($head !== null) {
        $result[] = $head->val;
        $head = $head->next;
    }
    return $result;
}

// Test case 1
$head = createLinkedList([1, 2, 3]);
$k = 5;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}

// Test case 2
$head = createLinkedList([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
$k = 3;
$result = splitListToParts($head, $k);
foreach ($result as $part) {
    print_r(printList($part));
}
?>

解释：

1. 计算长度：我们首先遍历链表求其长度。

2. 确定零件:

   • 我们将part_size计算为长度// k，这给出了每个部分应具有的最小尺寸。
   • 我们将 extra_nodes 计算为长度 % k，它给出了应该有一个额外节点的部分的数量。

3. 拆分列表：我们循环遍历 k 个部分并拆分列表：

   • 对于每个部分，如果应该有额外的节点，则分配part_size + 1个节点，否则只分配part_size。
   • 在每个部分的末尾，我们断开与列表其余部分的链接。

4. 处理空部分：如果节点数少于 k，则剩余部分将为 null（空）。

测试用例

• 示例1：

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

• 示例2：

   $head = [1,2,3,4,5,6,7,8,9,10]; $k = 3;
   Output: [[1,2,3,4],[5,6,7],[8,9,10]]

该解决方案有效地将链表拆分为 k 个部分，时间复杂度为 (O(n + k))，其中 n 是列表的长度。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。将链表拆分为多个部分的详细内容。更多信息请关注PHP中文网其他相关文章！