No.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份，如果不知道链表的长度，肯定没法划分，所以必须得先遍历一遍获得链表的长度len。

在获取了len之后，必须 在获取长度之后，$partlen=len/k$，这一句话的意思就是均分长度，但不考虑多余的部分，比如长度为10的分成3份，每一份的基础长度是3，余1，多出来的这个1加到了其中的一个3上，就变成了[4,3,3]这样的形式。余数在代码中就是remains这个变量。

然后思路就很明确了，为了方便实现了一个划分函数，干两件事，划分链表，返回划分后的链表和划分出来的部分链表。 一个示例：原链表head是[1,2,3,4,5]， cut(head,3)之后返回[1,2,3]并且head变成了[4,5]。这么处理会在最终形成答案的时候比较方便。 最后还要特判一下为空指针的情况，否则可能会出现错误。

C++代码

class Solution {
public:
    ListNode * cut(ListNode *& node, int cutlen) {
        ListNode * res = node;
        for (int i = 0; i < cutlen - 1; ++i) node = node->next;
        ListNode * hold = node;
        node = node->next;
        hold->next = nullptr;
        return res;
    }
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        if (!head) return vector<ListNode *>(k, nullptr);
        ListNode * cur = head;
        int len = 0;
        while (cur) {
            cur = cur->next;
            len++;
        }
        int partlen = len / k, remains = len - k * partlen, i = 0;
        vector<ListNode *> res(k);
        for (; i < remains; ++i) res[i] = cut(head, partlen + 1);
        for (; i < k; ++i) if (partlen) res[i] = cut(head, partlen);
        return res;
    }
};