LC 725. 分隔链表

题目描述

这是 LeetCode 上的 725. 分隔链表 ，难度为 中等。

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 $1$ 。这可能会导致有些部分为 null 。

这 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 <= Node.val <= 1000
• 1 <= k <= 50

---

模拟

根据题意，我们应当近可能将链表平均分为 $k$ 份。

我们可以采取与 (题解) 68. 文本左右对齐 类似的思路（在 $68$ 中，填充空格的操作与本题一致：尽可能平均，无法均分时，应当使前面比后面多）。

回到本题，我们可以先对链表进行一次扫描，得到总长度 $cnt$，再结合需要将将链表划分为 $k$ 份，可知每一份的 最小 分配单位 $per = \left \lfloor \frac{cnt}{k} \right \rfloor$（当 $cnt < k$ 时，$per$ 为 $0$）。

然后从前往后切割出 $k$ 份链表，由于是在原链表的基础上进行，因此这里的切分只需要在合适的位置将节点的 $next$ 指针置空即可。

当我们需要构造出 $ans[i]$ 的链表长度时，首先可以先分配 $per$ 的长度，如果 已处理的链表长度 + 剩余待分配份数 * per < cnt，说明后面「待分配的份数」如果按照每份链表分配 $per$ 长度的话，会有节点剩余，基于「不能均分时，前面的应当比后面长」原则，此时只需为当前 $ans[i]$ 多分一个单位长度即可。

代码：

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        // 扫描链表，得到总长度 cnt
        int cnt = 0;
        ListNode tmp = head;
        while (tmp != null && ++cnt > 0) tmp = tmp.next;
        // 理论最小分割长度
        int per = cnt / k;
        // 将链表分割为 k 份（sum 代表已经被处理的链表长度为多少）
        ListNode[] ans = new ListNode[k];
        for (int i = 0, sum = 1; i < k; i++, sum++) {
            ans[i] = head;
            tmp = ans[i];
            // 每次首先分配 per 的长度
            int u = per;
            while (u-- > 1 && ++sum > 0) tmp = tmp.next;
            // 当「已处理的链表长度 + 剩余待分配份数 * per < cnt」，再分配一个单位长度
            int remain = k - i - 1;
            if (per != 0 && sum + per * remain < cnt && ++sum > 0) tmp = tmp.next;
            head = tmp != null ? tmp.next : null;
            if (tmp != null) tmp.next = null; 
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.725 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。