LeetCode 725. Split Linked List

@(LeetCode)

问题描述

给定一个单链表的头节点 root，写一个函数将链表分为 k 个连续的链表分组。

每个分组中链表的长度应该尽量相等，且两个分组的长度差不超过 1。这会导致一些分组是 null。

分组应该按照链表节点出现的顺序来划分，并且前面的分组长度大于等于其后的分组。

返回一个数组，每个元素是分组的头结点。

栗 1：

输入：root = [1, 2, 3], k = 5
输出：[[1],[2],[3],[],[]]

解释：
链表长度为 3，分为 5 个分组，那么每个分组的节点个数为 [1, 1, 1, 0, 0]。每个节点单独为一组，多余的分组为 null。

栗 2：

输入：root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出：[[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释：
链表长度为 10，分为 3 个分组，那么每个分组的节点个数为 [4, 3, 3]。

注意：

• 链表的长度在 [0, 1000] 范围内。
• 每个节点的值为整数，范围是 [0, 999]。
• k 是整数，范围是 [1, 50]。

想看英文描述戳这里。

解题思路

这道题的解法比较常规。简单说下思路：

1. 若要把链表分组，那么得求出链表的长度 len。

2. 链表长度跟每个分组中的节点个数有关系，分为如下两种情况：

• 当 len < k 时，每个节点单独为一组，剩余的分组补上 null。

• 当 len >= k 时，需要计算是否能平均分配。如果不能，则需将多出的个数重新分配到前面分组。

  举个栗子：
  假设 len = 10，k = 4，那么平均每组为 10 / 4 = 2 个，即为 [2, 2, 2, 2]， 但还余 2 个。

  根据题意，由于前面的分组节点数 >= 后面的分组节点数，所以只能加上前面的 2 个分组中，一组多加 1 个，即 [3, 3, 2, 2]，

3. 根据每个分组的节点个数，遍历链表，找到其对应的头结点。

   这里需要注意一点，每个分组中的链表尾节点需要切断原有联系，否则一直会链接到原链表尾。

完整代码可点此查看。