原文链接: https://leetcode-cn.com/problems/split-linked-list-in-parts

英文原文

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null.

The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later.

Return an array of the k parts.

 

Example 1:

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

 

Constraints:

• The number of nodes in the list is in the range [0, 1000].
• 0 <= Node.val <= 1000
• 1 <= k <= 50

中文题目

给你一个头结点为 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)$

---

其他与「链表」相关内容

可以尝试加练下面的「链表」问题：

题目	题解	难度	推荐指数
2. 两数相加	LeetCode 题解链接	中等	🤩🤩🤩
19. 删除链表的倒数第 N 个结点	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
21. 合并两个有序链表	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
23. 合并K个升序链表	LeetCode 题解链接	困难	🤩🤩🤩
24. 两两交换链表中的节点	LeetCode 题解链接	中等	🤩🤩🤩🤩
25. K 个一组翻转链表	LeetCode 题解链接	困难	🤩🤩
61. 旋转链表	LeetCode 题解链接	中等	🤩🤩🤩
83. 删除排序链表中的重复元素	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
82. 删除排序链表中的重复元素 II	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
92. 反转链表 II	LeetCode 题解链接	中等	🤩🤩🤩
138. 复制带随机指针的链表	LeetCode 题解链接	中等	🤩🤩🤩
160. 相交链表	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
146. LRU 缓存机制	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
203. 移除链表元素	LeetCode 题解链接	简单	🤩🤩🤩
460. LFU 缓存	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
1600. 皇位继承顺序	LeetCode 题解链接	中等	🤩🤩🤩
剑指 Offer 22. 链表中倒数第k个节点	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩
剑指 Offer 52. 两个链表的第一个公共节点	LeetCode 题解链接	简单	🤩🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
49913	82039	60.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
旋转链表	中等
奇偶链表	中等