题目

标题和出处

标题：将链表分隔成 K 个部分

出处：725. 将链表分隔成 K 个部分

难度

5 级

题目描述

要求

给你单链表的头结点 和一个整数 ，将链表分隔成 个连续的部分。

每部分的长度应尽可能相等：任意两部分的长度相差不超过 。可能有些部分为 。

每个部分的顺序应和输入链表的顺序相同，并且前面部分的长度应总是大于或等于后面部分的长度。

返回分隔成的 个部分的数组。

示例

示例 1：

输入：
输出：
解释：
第一个元素 满足 ，。
最后一个元素 是 ，空链表的字符串表示是 。

示例 2：

输入：
输出：
解释：
输入链表被分隔成连续的部分，每部分的长度相差不超过 ，前面部分的长度大于或等于后面部分的长度。

数据范围

• 链表中结点的数目在范围 内
• 
• 

解法

思路和算法

由于每个部分的长度和原始链表的长度有关，因此需要遍历原始链表得到原始链表的长度，即结点数。

记原始链表的长度为 ，令 ，，则分隔成的 个部分中，前面 个部分的长度为 ，其余 个部分的长度为 。

将原始链表分隔成 个部分的做法是，找到每个部分的头结点和尾结点，将每个部分的头结点存入结果链表，并将每个部分的尾结点和后一个部分的头结点的连接关系断开。

用 表示当前遍历到的结点，初始时 。对于每个部分进行如下操作：

1. 当前部分的头结点即为 ，将 存入结果数组的对应下标处；
2. 计算得到该部分的长度 ；
3. 将 向后移动 次，此时 位于该部分的尾结点；
4. 记录 ，则 为后一个部分的头结点；
5. 令 ，将当前部分的尾结点和后一个部分的头结点的连接关系断开；
6. 令 ，此时 位于后一个部分的头结点，重复上述操作。

分隔链表的结束条件是 个部分全部分隔完毕，或者链表遍历结束。当链表长度大于或等于 时，每个部分至少有 个结点，因此需要将 个部分全部分隔完毕。当链表长度小于 时，分隔成的 个部分中，前面 个部分的长度都是 ，其余的 个部分都是空链表，因此当链表遍历结束时即完成分隔。

代码

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        int quotient = length / k, remainder = length % k;
        ListNode[] parts = new ListNode[k];
        curr = head;
        for (int i = 0; i < k && curr != null; i++) {
            parts[i] = curr;
            int partLength = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partLength; j++) {
                curr = curr.next;
            }
            ListNode next = curr.next;
            curr.next = null;
            curr = next;
        }
        return parts;
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=U6vV0)，其中 是链表的长度。需要遍历链表两次，第一次遍历得到链表的长度，第二次遍历分隔链表，分隔链表时对于每个结点的操作的时间都是 #card=math&code=O%281%29&id=rEbth)。
• 空间复杂度：#card=math&code=O%281%29&id=W89B4)。除了返回值以外，使用的空间复杂度是常数。